wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> det of gcd
        
(Message started by: Eigenray on Jul 15th, 2008, 8:51am)
Title: det of gcd
Post by Eigenray on Jul 15th, 2008, 8:51am
Find the determinant of the n x n matrix A defined by Ai,j = gcd(i,j).
Title: Re: det of gcd
Post by Barukh on Jul 15th, 2008, 10:07am
This problem looks very similar to me... I swear I saw it on this site, but cannot find it now...

I remeber the answer has something to do with [hide]totient function[/hide].

:-/
Title: Re: det of gcd
Post by Hippo on Jul 15th, 2008, 12:15pm
It seems to be http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gifin http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(i).
Title: Re: det of gcd
Post by Eigenray on Jul 16th, 2008, 1:56pm
Yes, that is correct.  Do you have a proof?

I also thought this problem was here already, but I tried searching various combinations of det, determinant, gcd, hcf, matrix, phi, etc.  Maybe it disappeared?
Title: Re: det of gcd
Post by Eigenray on Jul 16th, 2008, 2:40pm
How about:

Bi,j = i/gcd(i,j) = lcm(i,j)/j
Li,j = lcm(i,j)
Mi,j = i mod j, j>1;  Mi,1=1.

What are some good binary number-theoretic functions?

(There are some other arithmetic matrix problems [link=http://www.ocf.berkeley.edu/%7Ewwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1133057336]here[/link], [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1176335660]here[/link], and [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1139008533]here[/link].)
Title: Re: det of gcd
Post by Barukh on Jul 22nd, 2008, 1:28am

on 07/16/08 at 13:56:08, Eigenray wrote:
Yes, that is correct.  Do you have a proof?

After knowing the answer, several approaches are possible…

One of the proofs uses the Determinant Expansion by Minors (http://mathworld.wolfram.com/DeterminantExpansionbyMinors.html) (DEM). Although it’s not the easiest way to solve this problem, I would like to explore it here, since it gets at the answer from the basic matrix operations (the proof is based on Smith’s argument from back to 1876).

The idea is replace the n-th column of the matrix A(n) by linear combination of other columns in a way that all its elements but ann are equal to zero. Then, by the DEM, det(A(n)) = det(A(n-1)) ann.

Let p1, …, pm be distinct prime factors of n. As it is known, the totient function of n equals (http://en.wikipedia.org/wiki/Euler's_totient_function#Computing_Euler.27s_function):
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n) = n(1 – 1/p1)…(1 – 1/pm)

Now, if we open up the brackets in above formula, we will get a linear combination of 2m integers, half of them positive, and half negative (depending on the parity of pi’s in that term). Call the set of these integers the replacement vector. For example, when n = 6, the above formula gives 2 = 6 - 3 - 2 + 1, so the replacement vector is (1, -2, -3, 6).

Now, the replacement performed on the n-th column of matrix A(n) is as follows:

Replace the n-th column of A(n) by a signed sum of columns from replacement vector.

There is then a theorem stating that after such replacement, all elements of n-th column are equal to 0, except ann, which is just http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n). This actually gives the needed result.

In case n = 6, matrix A(6) has the following entries:

| 1  1  1  1  1  1 |
| 1  2  1  2  1  2 |
| 1  1  3  1  1  3 |
| 1  2  1  4  1  2 |
| 1  1  1  1  5  1 |
| 1  2  3  2  1  6 |

Applying the above replacement, means adding columns 1 and 6, and subtracting columns 2 and 3, which gives a new vector (0 0 0 0 0 2), as required.

How do we prove the above theorem? Denote the replacement of the element akn by R(k,n). The following statements apply (the derivation is mine  ;)):

1.  R(n, n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n).
2.  R(1, n) = 0 for n > 1.
3.  If q is a prime and R(k, n) = 0, then R(kq, nq) = 0.
4.  If R(k, n) = 0 and gcd(q, n) = 1, then R(kq, n) = 0.

Long and boring? Maybe, but I liked to go through all the steps of the proof.

Much more elegant proofs exist. One is based on factoring the given matrix to a special matrix and its transpose.
Title: Re: det of gcd
Post by Hippo on Jul 22nd, 2008, 8:07am

on 07/22/08 at 01:28:24, Barukh wrote:

This is almost how I have computed the result ;) ... Actually I do it transposed ;). I have seen the resulting uptriangle matrix with http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n) on diagonal (after elimination).
Title: Re: det of gcd
Post by Barukh on Jul 22nd, 2008, 10:15am

on 07/22/08 at 08:07:23, Hippo wrote:
This is almost how I have computed the result ;) ... Actually I do it transposed ;). I have seen the resulting uptriangle matrix with http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n) on diagonal (after elimination).

Nice work, Hippo!


on 07/22/08 at 01:28:24, Barukh wrote:
Much more elegant proofs exist. One is based on factoring the given matrix to a special matrix and its transpose.

The "civilized" proof goes like this (Beslin & Ligh, 89). Define an nxn matrix B = (bij) as follows: (B)ij = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(j), if j | i;  0, otherwise. B is a lower-triangular matrix with square roots of totient functions on the main diagonal.

Then (BBT)ij = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifkbikbjk = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif k|i, k|j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(k) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk|gcd(i,j) = gcd(i, j) = aij.

Therefore, det(A) = det(B)det(BT) = det(B)2, as required.
Title: Re: det of gcd
Post by Eigenray on Jul 22nd, 2008, 11:02am

on 07/22/08 at 01:28:24, Barukh wrote:
Now, if we open up the brackets in above formula, we will get a linear combination of 2m integers, half of them positive, and half negative (depending on the parity of pi’s in that term). Call the set of these integers the replacement vector. For example, when n = 6, the above formula gives 2 = 6 - 3 - 2 + 1, so the replacement vector is (1, -2, -3, 6).

In other words, this replacement vector is { http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif(d)*n/d }.  So you're right-multiplying by the matrix Sij = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif(j/i), if i | j.  In fact, St A S is diagonal :)  This was the proof I had in mind.


Quote:
Therefore, det(A) = det(B)det(BT) = det(B)2, as required.

That is very nice!  I was not aware of that one.
Title: Re: det of gcd
Post by Barukh on Jul 23rd, 2008, 12:45am

on 07/22/08 at 11:02:46, Eigenray wrote:
In other words, this replacement vector is { http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif(d)*n/d }.

Yes, of course! Very nice. It makes the whole argument much more simple.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board