6
$\begingroup$

Context (skippable)

I was asked (by a friend who is preparing for an exam) whether there was a special trick to compute the determinant of the following matrix. I didn't see anything beyond using the standard computations (like using "Gauss" to compute the value).

Then I asked another math student who, while quite bright, is a bit rusty in linear algebra and using sagemath we empirically found the below formula. Of course we were both confused as to a) whether it actually always holds and b) why it holds.

Actual question

Let $n\in\mathbb N$ be a positive integer. Let $I_n\in\mathbb R^{n\times n}$ be the identity matrix and let $1_n\in\mathbb R^{n\times n}$ be the all-one matrix, that is, the matrix for which every entry is $1$.
Now I am confused as to why the following (empirically found) statement holds (or does not):

$$\forall n\in\mathbb N:\det(1_n-I_n)=(-1)^{n-1}(n-1)$$


For illustration purposes, here is the matrix for $n=4$ (with the determinant being $-3$): \begin{pmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{pmatrix}

$\endgroup$

marked as duplicate by J. M. is a poor mathematician, Martin Sleziak, Hans Lundmark, Lord Shark the Unknown, Claude Leibovici Aug 14 '17 at 7:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

15
$\begingroup$

$1_n$ has eigenvalues $n$ with multiplicity $1$ and $0$ with multiplicity $n-1$, so $1_n - I_n$ has eigenvalues $n-1$ with multiplicity $1$ and $-1$ with multiplicity $n-1$. The determinant is the product of the eigenvalues, thus $(-1)^{n-1} (n-1)$.

$\endgroup$
8
$\begingroup$

\begin{align}\det (1_n-I_n)&=(-1)^{n}\det(I_n-1_n) \\ &=(-1)^n\det(I_n-ee^T)\\ &=(-1)^n(1-e^Te)\det(I_n)\\ &=(-1)^{n+1}(n-1)\end{align}

where I have used matrix determinant lemma in the third equality.

$\endgroup$
3
$\begingroup$

Here is a matrix (here with $n=10$) with columns that are eigenvectors of your (symmetric) matrix. Indeed, given any constants $\alpha, \beta,$ this shows a basis of eigenvectors for $\alpha I_n + \beta \, 1_n$

Note that $P$ is not orthogonal, although the columns are pairwise orthogonal. $$ P = \left( \begin{array}{rrrrrrrrrr} 1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 2 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 3 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 4 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 5 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 6 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 7 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 \end{array} \right). $$ You get an evident basis of eigenvectors, so you can tell the eigenvalues.

The columns of $P$ are of varying lengths; dividing each by its length does give an orthogonal matrix.

For $n=4$

$$ P = \left( \begin{array}{rrrr} 1 & -1 & -1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & 0 & 2 & -1 \\ 1 & 0 & 0 & 3 \end{array} \right). $$

$\endgroup$
  • $\begingroup$ why did you delete your answers? $\endgroup$ – Turbo Aug 15 '17 at 9:36
  • $\begingroup$ Will, Re: your deleted Meta question. I presume you found $(a,b,c,d)=(1,-3,3,-1)$ and that ruined the idea you had? $\endgroup$ – Jyrki Lahtonen Aug 15 '17 at 13:06
  • $\begingroup$ @JyrkiLahtonen actually, I found that and a closed form that produces it (after dividing through by the gcd if greater than one) $ a = At - Cu, \; \; b = Du - At, \; \; c = Cu - B t, \; \; d = Bt - Du. $ When ABCD are really close together, take $t=u=1.$ $\endgroup$ – Will Jagy Aug 15 '17 at 16:17
  • $\begingroup$ @JyrkiLahtonen thanks for looking into it. $\endgroup$ – Will Jagy Aug 15 '17 at 16:27
2
$\begingroup$

The other answers offer more insight into linear algebra. But you obviously wondered about whether you could use Gaussian elimination in some way — this is just to show you one possible way. Returning to your case $n=4$ as a worked example:

\begin{pmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{pmatrix}

It would be nice to procure a row or column in which there is only one non-zero entry. Let us try to eliminate all the ones that occupy the first $n-1=3$ columns in the bottom row. Above each of these ones sit $n-1=3$ entries, including one of the zeros on the diagonal, so there are always $n-2$ ones and one zero. On the other hand, above the zero in the bottom right there are $n-1$ ones. If we added all rows bar the bottom one, we get

$$R_1 + \dots + R_{n-1}= \begin{pmatrix} n-2&\cdots&n-2&n-1\\ \end{pmatrix}$$

Hence we subtract from the final row $\frac{1}{n-2}(R_1+\dots+R_{n-1})$ to obtain

\begin{pmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 0&0&0&-\frac{n-1}{n-2} \end{pmatrix}

where in this particular case, the bottom right entry would be $-\frac{n-1}{n-2}=-\frac{3}{2}$. If we then perform a Laplace (cofactor) expansion along the bottom row, we will need to find the determinant of the submatrix occupying the first $n-1$ rows and columns. But that submatrix is $1_{n-1} - I_{n-1}$, so we have reduced the problem to the previous case. The proof can therefore be carried out by induction.

The base case is easy enough to prove. And assuming the result is true for smaller cases, the argument outlined above gives:

$$\det(1_n - I_n) = (-1)^{n+n}\left(-\frac{n-1}{n-2}\right) \det (1_{n-1} - I_{n-1}) = (1)\left(-\frac{n-1}{n-2}\right)\left((-1)^{n-2}(n-2)\right)$$

which gives the required $(-1)^{n-1}(n-1)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.