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

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an 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

${\begin{bmatrix}a&-y\\b&x\end{bmatrix}}.$

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

${\begin{bmatrix}100&11&7\\45&5&3\\72&8&5\end{bmatrix}}.$

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

${\begin{bmatrix}b/d&p\\c/d&q\end{bmatrix}}.$

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

${\begin{bmatrix}a&r\\d&s\end{bmatrix}}.$

with determinant 1. Then the product

${\begin{bmatrix}1&&\\&b/d&p\\&c/d&q\end{bmatrix}}{\begin{bmatrix}a&r&\\d&s&\\&&1\end{bmatrix}}.$

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)