Simplest way to calculate a determinant [duplicate]

This question already has an answer here:

The big $1$'s here just mean that the lower and upper triangular entries are all $1$'s. The trace entries are all zero. The matrix is for a general $n\times n$ matrix of this form. I'm trying to deduce a simpler relation. $$\operatorname{det}~\begin{pmatrix} 0 & 1 & 1 & \cdots & 1 \\ 1 & 0 & 1 &\cdots & 1\\ 1 & 1 & 0 &\cdots & 1\\ \vdots & \vdots & \vdots & \ddots & 1\\ 1 & 1 & 1 & \cdots & 0\end{pmatrix}$$

marked as duplicate by user17762, Henry T. Horton, Andrés E. Caicedo, Pedro Tamaroff♦, vonbrandMay 11 '13 at 2:56

• That is some huge matrix. – Marra May 11 '13 at 2:07
• – user17762 May 11 '13 at 2:11
• Did you try inducting on the size of the matrix? – Pedro Tamaroff May 11 '13 at 2:48

Here is a very bizarre solution. Let

$$A = \begin{pmatrix}1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1 \end{pmatrix}$$

be an $n \times n$ matrix whose entries are identically $1$. Then $A^{k} = n^{k-1} A$ and we have

$$e^{t A} = I + \sum_{k=1}^{\infty} \frac{t^{k} n^{k-1}}{k!} A = I + \frac{e^{nt} - 1}{n} A.$$

But we know that

$$\det e^{t A} = e^{\operatorname{tr}(t A)} = e^{nt}.$$

Thus if we put $z = \frac{1}{n}(1 - e^{nt})$, then we have $z < \frac{1}{n}$ and

$$\det ( I - z A ) = 1 - nz.$$

But both sides are polynomials in $z$, and thus it must coincide for all $z$. Therefore by plugging $z = 1$, we have

$$\det (A - I) = (-1)^{n} \det ( I - A ) = (-1)^{n-1} (n - 1).$$

This argument can be used to prove that for any $\mathrm{u}, \mathrm{v} \in \Bbb{R}^n$, we have

$$\det (I + \mathrm{u} \mathrm{v}^{t}) = 1 + \mathrm{u}^{t}\mathrm{v},$$

a special case of the Sylvester's determinant theorem.

• That is what I was thinking. I have something similar to this written down somewhere. I came to the last result too. – Trancot May 11 '13 at 3:51

Note the matrix is nothing but $$ee^T - I_{n \times n}$$ where $e$ is the vector of $1$'s. All the relevant operation on this matrix, like solving linear systems, matrix vector products, computing the eigenvalues and determinant, etc., can be performed in linear complexity.