Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Dec 24, 2013

Determinant of Matrix (17-11)

Source: Mailed by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus)

Problem:

A is a 300 x 300 matrix with 17 on the diagonal, and the rest of the entries being 11. What is det (A) ?

Define M_n as the n x n matrix with diagonal entries all be x and the non-diagonal entries all y. Let D_n be the determinant of M_n and D_n' be the determinant of M_n' where M_n' is obtained from M_n by replacing the (1,1)-th entry by y.

To compute determinants, we only replace (row 1) -> (row 1)-(row 2) for both M_n and M_n'.

Then we have the following recursion: D_n = (x-y)(D_{n-1}+D_{n-1}') D_n'=(x-y) D_{n-1}'. Solving the recursion for D_n gives D_n=(x-y)^{n-1}(x+(n-1)y). Substituting n=300, x=17,y=11 gives D_{300}=6^300*19*29.

The easiest way to do this is by working out the eigendecomposition of a general matrix of this form. Consider a matrix of the form aI_n + bJ_n, where I_n is the n x n identity matrix, and J_n is the n x n matrix whose entries are identically one. The eigenvectors are the vector of ones and the basis of the orthogonal complement of the space spanned by the vector of ones. The eigenvalue corresponding to the vector of ones is a + nb, and the eigenvalue corresponding to any other eigenvector is a. The first eigenvalue has multiplicity one and the second has multiplicity n - 1, so the determinant is simply a^(n - 1) * (a + nb).

In this case, a = 6, b = 11 and n = 300, so the determinant is 6^299 * (6 + 300 * 11). We can rewrite that as 6^300 * (1 + 50 * 11). 551 = 19 * 29, so my answer agrees with the previous one.

It can be seen as a sum of a matrix with all 11s and a matrix with 6s on the diagonal.

That is the sum of a diagonal matrix and a rank one update to it. You can use http://en.wikipedia.org/wiki/Matrix_determinant_lemma, which gives (and kills the joy in the problem)

Given diagonal element x and off-diagonal y, Det = (x-y)^{n-1}(x+(n-1)y).

Here is a bit long but interesting solution. We agree on that it is enough to calculate f(x) = det( I + x N ), where N is matrix with all the entries 1. Note that N^2 = n N, where n is the dimension. Then, by det(AB) = det(A) det(B), it follows that f will satisfy functional equation f(x) f(y) = f( x+ y + nxy ) . Also, f is a polynomial with f(0) = 1. Now you can use standard calculus to solve this functional equation to get the answer f(x) = 1 + nx . Of course, we have to argue that f is not equal to constant function 1. But, this is not a problem because if this was the case, characterstic polynomial of N will have all the coffiecient zero expect the leading term. But the trace of N is non zero.

First we agree on that it is enough to calculate f(x) = det( I + x N ), where N is matrix with all entries 1. Then by det(AB) = det (A) det(B), we see that f is a polynomial satisfying f(x) f(y) = f( x + y + nxy) with f(0) = 1. Now we can use standard calculus to solve this functional equation. Of course, we have to argue that f is not the constant function 1. But this is ok because if it was the case, characteristic polynomial of N will have all the coefficient 0 except the leading one. But the trace of N is non zero. So, we get f(x) = 1+ nx

Define M_n as the n x n matrix with diagonal entries all be x and the non-diagonal entries all y. Let D_n be the determinant of M_n and D_n' be the determinant of M_n' where M_n' is obtained from M_n by replacing the (1,1)-th entry by y.

ReplyDeleteTo compute determinants, we only replace (row 1) -> (row 1)-(row 2) for both M_n and M_n'.

Then we have the following recursion:

D_n = (x-y)(D_{n-1}+D_{n-1}')

D_n'=(x-y) D_{n-1}'.

Solving the recursion for D_n gives D_n=(x-y)^{n-1}(x+(n-1)y).

Substituting n=300, x=17,y=11 gives D_{300}=6^300*19*29.

The easiest way to do this is by working out the eigendecomposition of a general matrix of this form. Consider a matrix of the form aI_n + bJ_n, where I_n is the n x n identity matrix, and J_n is the n x n matrix whose entries are identically one. The eigenvectors are the vector of ones and the basis of the orthogonal complement of the space spanned by the vector of ones. The eigenvalue corresponding to the vector of ones is a + nb, and the eigenvalue corresponding to any other eigenvector is a. The first eigenvalue has multiplicity one and the second has multiplicity n - 1, so the determinant is simply a^(n - 1) * (a + nb).

ReplyDeleteIn this case, a = 6, b = 11 and n = 300, so the determinant is 6^299 * (6 + 300 * 11). We can rewrite that as 6^300 * (1 + 50 * 11). 551 = 19 * 29, so my answer agrees with the previous one.

It can be seen as a sum of a matrix with all 11s and a matrix with 6s on the diagonal.

ReplyDeleteThat is the sum of a diagonal matrix and a rank one update to it. You can use http://en.wikipedia.org/wiki/Matrix_determinant_lemma, which gives (and kills the joy in the problem)

Given diagonal element x and off-diagonal y, Det = (x-y)^{n-1}(x+(n-1)y).

Here is a bit long but interesting solution.

ReplyDeleteWe agree on that it is enough to calculate f(x) = det( I + x N ), where N is matrix with all the entries 1. Note that

N^2 = n N, where n is the dimension. Then, by det(AB) = det(A) det(B), it follows that f will satisfy functional equation f(x) f(y) = f( x+ y + nxy ) . Also, f is a polynomial with f(0) = 1. Now you can use standard calculus to solve this functional equation to get the answer f(x) = 1 + nx . Of course, we have to argue that f is not equal to constant function 1. But, this is not a problem because if this was the case, characterstic polynomial of N will have all the coffiecient zero expect the leading term. But the trace of N is non zero.

First we agree on that it is enough to calculate f(x) = det( I + x N ), where N is matrix with all entries 1. Then by

ReplyDeletedet(AB) = det (A) det(B), we see that f is a polynomial satisfying f(x) f(y) = f( x + y + nxy) with f(0) = 1. Now we can use standard calculus to solve this functional equation. Of course, we have to argue that f is not the constant function 1. But this is ok because if it was the case, characteristic polynomial of N will have all the coefficient 0 except the leading one. But the trace of N is non zero. So, we get f(x) = 1+ nx