Testwiki:Reference desk/Archives/Mathematics/2013 October 4

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < October 3 ! width="25%" align="center"|<< Sep | October | Nov >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 4

Absolute value (algebra)

In this article, I don't understand what the "No-Solution Case" section is trying to say. It looks like it is trying to say that the absolute value is never negative, but I could be wrong. At any rate, it seems out of place with the rest of the article; the talk page doesn't seem much visited, so I figured I'd ask here. I don't want to remove/edit something if I've missed something- maybe it's something commonly seen in textbooks that needs to be reworded? Thanks:-)Phoenixia1177 (talk) 05:23, 4 October 2013 (UTC)

It might be an attempt at adding what you just said, but it is borderline incoherent as written. I've reverted it. --Kinu ^t/_c 05:42, 4 October 2013 (UTC)

Thanks. I was figuring that'd be the best course, just wanted to make sure I wasn't glossing over/forgetting something.Phoenixia1177 (talk) 05:55, 4 October 2013 (UTC)

Possible columns in an integral matrix

This probably has a very easy answer and I'm just being dense. It is clear that a necessary and sufficient condition for a pair of non-zero integers to appear as a column in some invertible 2 x 2 integral matrix (edit: whose inverse is integral) is that their greatest common divisor is 1. Does this property hold for n-tuples of non-zero integers when considering invertible n x n integral matrices for larger n? It's clearly still a necessary condition. I feel if I hadn't forgotten all my basic module theory, I'd be able to answer this pretty quickly! Thanks, Icthyos (talk) 17:19, 4 October 2013 (UTC)

Unless I'm missing something, the premise is not true. Consider:

 1  2
 0  4

That's invertible, isn't it? Looie496 (talk) 17:58, 4 October 2013 (UTC)

Ack, sorry, I only ever work with integral matrices, so forgot to specify that I require the inverse to be integral too (i.e. the determinant must be 1 or -1). Icthyos (talk) 18:06, 4 October 2013 (UTC)

(ec)To answer the revised question, see Extended Euclidean algorithm for the 2 by 2 case. Two integers a and b are relatively iff there exist integers x and y so that ax+by=1. But ax+by is the determinant of

$\left[\begin{array}{cc}a& -y\\ b& x\end{array}\right].$

There is a similar theorem that says if a, b, c, ... n are relatively prime (as a group, not necessarily in pairs), iff there exist p, q, r, ... z so that ap+bq+cz+...+nz=1. But this isn't in the form of a determinant so I think something a bit stronger is needed, such as:

A vector (a, b, c, ... n) of integers is a column of a square integer matrix of determinant 1 iff the gcd of a, b, c, ... n is 1.

I've sketched out a proof of this following the method use in the Euclidean algorithm, but it's rather long to post here, plus I assume the result is easier to obtain using more sophisticated methods. --RDBury (talk) 19:40, 5 October 2013 (UTC)

It seems to me that gcd(all elements of the column)=1 should be sufficient. Consider the column (a b c)^T for given a, b, c. Find d, e, f, g, h, and i such that the matrix

a d g

b e h

c f i

has determinant = 1. If my unchecked algebra is correct, setting this determinant to unity and solving for d gives

$d=\frac{a(ei-fh)+b(fg)-c(eg)-1}{bi-ch}.$

Now setting the denominator of this equal to 1 is the same as the problem in one lower dimension of finding i, h that make

b h

c i

have a unit determinant. Since this can be done, we can make our denominator equal to 1; then use any integer e, f, g in the numerator and use the equation to get the resulting integer d.

So it looks to me like you could generate a proof by induction for successively larger problem sizes, the sufficiency proof for each being dependent on the sufficiency in the problem of one dimension lower. Duoduoduo (talk) 19:13, 5 October 2013 (UTC)

Actually this assumes that some pair of a, b, and c is relatively prime, but in the case 100, 45, 72, the numbers are relatively prime as a group but not in pairs. However

$\left[\begin{array}{ccc}100& 11& 7\\ 45& 5& 3\\ 72& 8& 5\end{array}\right].$

has determinant 1, so having a pair of relatively prime entries isn't needed. --RDBury (talk) 19:51, 5 October 2013 (UTC)

Okay, so my post above shows that a sufficient condition for the 3×3 case is that at least one pair of the entries be coprime. So the question remains: is the alternative condition gcd(a, b, c) = 1 also sufficient? I.e., it works in the case (100, 45, 72), but does it work in all such cases? Duoduoduo (talk) 22:19, 5 October 2013 (UTC)

Here's a proof that's a bit better than the one I was talking about above. I'll do the dim 2 => dim 3 case which easily generalizes to dim n => dim n+1. We are given a,b,c with gcd(a,b,c)=1. Let d=gcd(b,c). then gcd(b/d, c/d) = 1 and there is a matrix

$\left[\begin{array}{cc}b/d& p\\ c/d& q\end{array}\right].$

with determinant 1. gcd(a,d)=1 so there is a second matrix

$\left[\begin{array}{cc}a& r\\ d& s\end{array}\right].$

with determinant 1. Then the product

$\left[\begin{array}{ccc}1& & \\ & b/d& p\\ & c/d& q\end{array}\right]\left[\begin{array}{ccc}a& r& \\ d& s& \\ & & 1\end{array}\right].$

has determinant 1 and the first column is (a, b, c).

I believe this can be generalized as follows: Let R be a p.i.d. and let F be a free, finitely generated R-module. If L is a submodule of F so that F/L is torsion free then L is a direct summand of F. This is an application of the theory of modules over a p.i.d. --RDBury (talk) 00:17, 6 October 2013 (UTC)

Ah-hah! Very clever. Thank you both for your replies. Icthyos (talk) 11:08, 6 October 2013 (UTC)