Linear Algebra I: Determinants & Structured Matrices

Proof idea: $\mathbf u\mathbf v^{\mathsf T}$ has rank $1$ with the single nonzero eigenvalue $\mathbf v^{\mathsf T}\mathbf u$ (eigenvector $\mathbf u$), so $I + \mathbf u\mathbf v^{\mathsf T}$ has eigenvalues $1 + \mathbf v^{\mathsf T}\mathbf u$ and $1$ (repeated). The $5\times5$ matrix with $2$ on the diagonal and $1$ elsewhere is $I + J$: determinant $6$. Matrices with entries $a_i + b_j$ have rank $\le 2$ (entries $i + j$: rank exactly $2$); entries $a_ib_j$ give rank $1$. Recognize low rank and the determinant is $0$ before any computation.

Vandermonde is why $n + 1$ points determine a degree-$n$ polynomial (the interpolation matrix is invertible iff the $x_i$ are distinct). Circulants are diagonalized by the Fourier matrix, so their determinants are products of polynomial values at roots of unity — how $\det$ of "$a$ on the diagonal, $b$ next to it, cyclically" becomes $\prod_k(a + b\omega^k + b\omega^{-k})$. Tridiagonal determinants satisfy a three-term recurrence $D_n = aD_{n-1} - b^2D_{n-2}$, which is why their eigenvalues are cosines.

Expand: $(i-j)^2 = i^2 - 2ij + j^2$ — a sum of THREE rank-one matrices ($i^2\cdot1$, $i\cdot j$, $1\cdot j^2$), so rank $\le 3$; and it is exactly $3$ (the three are independent for $n \ge 3$). Any matrix whose entries are a polynomial in $i$ and $j$ of total degree $d$ has rank at most $d + 1$.

Block-matrix proof: the identity $\begin{pmatrix} I & 0 \\ \mathbf v^{\mathsf T} & 1\end{pmatrix}\begin{pmatrix} I + \mathbf u\mathbf v^{\mathsf T} & \mathbf u \\ 0 & 1\end{pmatrix}\begin{pmatrix} I & 0 \\ -\mathbf v^{\mathsf T} & 1\end{pmatrix} = \begin{pmatrix} I & \mathbf u \\ 0 & 1 + \mathbf v^{\mathsf T}\mathbf u\end{pmatrix}$ holds by direct multiplication; take determinants of both sides (the outer factors are unitriangular, determinant $1$; the right side is block triangular) to get $\det(I + \mathbf u\mathbf v^{\mathsf T}) = 1 + \mathbf v^{\mathsf T}\mathbf u$. For the general form factor $A + \mathbf u\mathbf v^{\mathsf T} = A(I + A^{-1}\mathbf u\mathbf v^{\mathsf T})$. $\blacksquare$ Significance: every "all entries equal except the diagonal" determinant, and every rank-one perturbation, is one line — $\det(aI + bJ) = a^{n-1}(a + nb)$ is the case $\mathbf u = b\mathbf 1$, $\mathbf v = \mathbf 1$.

View the determinant as a polynomial $P$ in the variables $x_1, \ldots, x_n$. If $x_i = x_j$ two rows coincide and $P = 0$, so $(x_j - x_i)$ divides $P$ for every pair; these $\binom n2$ linear factors are pairwise coprime, so their product $Q$ divides $P$. Both $P$ and $Q$ have total degree $0 + 1 + \cdots + (n-1) = \binom n2$, hence $P = cQ$ for a constant $c$; comparing the coefficient of the monomial $x_2x_3^2\cdots x_n^{n-1}$ (the main diagonal term in $P$, and the product of the leading terms in $Q$) gives $c = 1$. $\blacksquare$ Significance: Vandermonde is nonzero iff the nodes are distinct, which is exactly why polynomial interpolation through distinct points is unique — Lagrange interpolation is this determinant's invertibility.

Expand along the first row: the $(1,1)$ cofactor is $\det T_{n-1}$; the $(1,2)$ entry $b$ has a cofactor whose first column contains only $c$ (in its first row), and expanding that along its first column leaves $-bc\det T_{n-2}$. For the eigenvalues, try $\mathbf x = (\sin\theta, \sin 2\theta, \ldots, \sin n\theta)$: the identity $\sin(j-1)\theta + \sin(j+1)\theta = 2\cos\theta\sin j\theta$ shows $T_n\mathbf x = (a + 2b\cos\theta)\mathbf x$ provided the boundary terms vanish, i.e. $\sin(n+1)\theta = 0$, which gives $\theta = \frac{k\pi}{n+1}$. $\blacksquare$ Significance: $T_n$ with $a = 2$, $b = c = -1$ is the discrete Laplacian; its determinant $n + 1$ and its spectrum $2 - 2\cos\frac{k\pi}{n+1}$ appear in resistor networks, random walks, and the Putnam every few years.

The block identity $\begin{pmatrix}I & 0\\ \mathbf v^{\mathsf T} & 1\end{pmatrix}\begin{pmatrix}I + \mathbf u\mathbf v^{\mathsf T} & \mathbf u\\ 0 & 1\end{pmatrix}\begin{pmatrix}I & 0\\ -\mathbf v^{\mathsf T} & 1\end{pmatrix} = \begin{pmatrix}I & \mathbf u\\ 0 & 1 + \mathbf v^{\mathsf T}\mathbf u\end{pmatrix}$ has determinant $1 + \mathbf v^{\mathsf T}\mathbf u$ on the right and $\det(I + \mathbf u\mathbf v^{\mathsf T})$ on the left (the outer factors are unit triangular). $\blacksquare$ Significance: with $A$ in place of $I$, $\det(A + \mathbf u\mathbf v^{\mathsf T}) = \det A\,(1 + \mathbf v^{\mathsf T}A^{-1}\mathbf u)$ — the tool behind Sherman–Morrison updates in numerical linear algebra and half the Putnam determinant problems.

View the determinant as a polynomial in $x_n$: it has degree $n - 1$ and vanishes whenever $x_n = x_i$ for $i < n$ (two equal rows), so it equals $c\prod_{i<n}(x_n - x_i)$ with $c$ independent of $x_n$; comparing the coefficient of $x_n^{n-1}$ (expand along the last row) shows $c$ is the $(n-1)\times(n-1)$ Vandermonde. Induct. $\blacksquare$ Significance: the product is nonzero iff the $x_i$ are distinct — polynomial interpolation is unique, and the roots-of-unity Vandermonde is (up to scale) the unitary Fourier matrix.

Step 1 — expand along the first row: $D_n = 2D_{n-1} - 1\cdot D_{n-2}$ (the second term comes from the $1$ in position $(1,2)$, whose minor expands to $D_{n-2}$).

Step 2 — $D_1 = 2$, $D_2 = 3$; the recurrence $D_n = 2D_{n-1} - D_{n-2}$ has characteristic root $1$ (double), so $D_n = A + Bn$.

Step 3 — fit: $A + B = 2$, $A + 2B = 3$ gives $D_n = n + 1$.

Step 4 — cross-check with the eigenvalue formula: $\prod_{k=1}^n\left(2 + 2\cos\tfrac{k\pi}{n+1}\right) = \prod 4\cos^2\tfrac{k\pi}{2(n+1)} = n + 1$, a known product identity ✓.

Step 1 — Vandermonde: the determinant is $(b - a)(c - a)(c - b)$.

Step 2 — three points $(x_i, y_i)$ are collinear iff $\det[1, x_i, y_i] = 0$ (the rows are then linearly dependent — the standard area formula).

Step 3 — with $y_i = x_i^2$ that determinant is the Vandermonde, nonzero for distinct $a, b, c$. Hence no three distinct points of a parabola are collinear.

Step 4 — the same argument shows a degree-$n$ polynomial's graph meets no line in more than $n$ points — Vandermonde is the algebraic form of "a polynomial has at most $n$ roots."