University Mathematics — Year 1 · Bachelor Year 1

22Determinants and Linear Systems

The determinant condenses into one scalar the answer to “are these $n$ vectors a basis?” — and, geometrically, measures the volume they span. We characterize it by its properties (multilinear, alternating, normalized), compute it in dimensions $2$ and $3$ and by cofactor expansion in general, and put it to work on linear systems, alongside the all-purpose algorithm: Gaussian elimination.

22.1 The determinant

Theorem 22.1 (Characterization)

There is exactly one map $\det \colon \mathcal{M}_n(K) \to K$ , viewed as a function of the $n$ columns, that is:

linear in each column (the others fixed);
alternating: swapping two columns changes the sign (hence two equal columns give $0$ );
normalized: $\det I_n = 1$ .

For $n = 2$ and $3$ :

\begin{vmatrix} a & b\\ c & d\end{vmatrix} = ad - bc, \qquad \begin{vmatrix} a & b & c\\ d & e & f\\ g & h & i\end{vmatrix} = aei + bfg + cdh - ceg - bdi - afh

(the $3 \times 3$ rule of Sarrus: products of descending diagonals minus ascending ones).

Proof. Admitted at this level. ∎

Remark 22.2

For $n = 2$ : expanding by bilinearity on the canonical columns gives the formula, which conversely satisfies the axioms — a complete proof; $n = 3$ is identical with more terms. The general case (existence via the sum over permutations, uniqueness by the same expansion) demands the signature of a permutation and is deferred to the second year; we freely use the axioms and the consequences below.

The $n = 2$ expansion in full, since it is the template: with columns $C_1 = a\,e_1 + c\,e_2$ and $C_2 = b\,e_1 + d\,e_2$ , bilinearity gives

\det(C_1, C_2) = ab\det(e_1, e_1) + ad\det(e_1, e_2) + cb\det(e_2, e_1) + cd\det(e_2, e_2),

and alternation kills the repeated pairs while flipping $\det(e_2, e_1) = -\det(e_1, e_2)$ : the whole map collapses to $(ad - bc)\det(e_1, e_2) = ad - bc$ by normalization. Uniqueness is visible in the computation itself — the axioms left no choice at any step — and this is exactly the scaled-uniqueness fact used in the proof of the product rule below.

Theorem 22.3 (Properties)

For $A, B \in \mathcal{M}_n(K)$ :

adding to a column a multiple of another does not change the determinant; multiplying a column by $\lambda$ multiplies it by $\lambda$ (so $\det(\lambda A) = \lambda^n \det A$ );
$\det(AB) = \det A\, \det B$ ;
$A$ is invertible $\iff$ $\det A \neq 0$ $\iff$ the columns form a basis of $K^n$ ; and then $\det(A^{-1}) = (\det A)^{-1}$ ;
$\det(A^{\mathsf T}) = \det A$ — so every column rule is also a row rule;
the determinant of a triangular matrix is the product of its diagonal entries.

Proof. (1) By linearity, $\det(\dots, C_i + \lambda C_j, \dots) = \det A + \lambda\det(\dots, C_j, \dots)$ where the second determinant has two equal columns: zero.

(2) Fix $A$ and consider $\varphi(B) = \det(AB)$ as a function of the columns of $B$ : since $AB$ has columns $AB_j$ , $\varphi$ is multilinear and alternating in the $B_j$ . We admit, with Theorem 22.1, its uniqueness statement in scaled form: every multilinear alternating map $\varphi$ of the columns equals $\varphi(I_n) \cdot \det$ . Here $\varphi(I_n) = \det A$ , so $\det(AB) = \det A \cdot \det B$ .

(3) If $A$ is invertible: $\det A\,\det A^{-1} = \det I = 1$ , so $\det A \neq 0$ and the inverse formula holds. If $A$ is not invertible, its columns are linked (Corollary 20.9 and Proposition 20.2); expressing one column through the others and expanding by linearity leaves determinants with two equal columns: $\det A = 0$ . The basis statement is Proposition 19.8.

(4) Admitted with the general construction (it is immediate on the permutation formula); we record it to use row operations.

(5) If some diagonal entry vanishes, the first $k$ columns are linked for some $k$ (rank considerations) and $\det = 0 =$ product. Otherwise, clear each column below-and-left by operations of type (1) — possible in the triangular shape — reaching the diagonal matrix, whose determinant is the product of the entries by multilinearity from $I_n$ . ∎

Example 22.4 (The rules, checked on numbers)

Take $A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ ( $\det A = -2$ ) and $B = \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix}$ ( $\det B = -1$ ). Then

AB = \begin{pmatrix} 2 & 3\\ 4 & 7\end{pmatrix}, \quad \det(AB) = 14 - 12 = 2 = (-2)(-1) ; \qquad \det(A^{\mathsf T}) = \begin{vmatrix} 1 & 3\\ 2 & 4 \end{vmatrix} = -2 = \det A .

Multiplicativity and transpose-invariance confirmed — while the false additivity fails on the same pair:

\det(A + B) = \begin{vmatrix} 1 & 3\\ 4 & 5\end{vmatrix} = -7 \neq \det A + \det B = -3 .

Thirty seconds of arithmetic of this kind, after any determinant identity is invoked, is the cheapest error insurance available.

Example 22.5 (Determinants as areas)

The parallelogram spanned by $u = (2, 0)$ and $v = (1, 3)$ has base $2$ and height $3$ : area $6$ . And

\begin{vmatrix} 2 & 1\\ 0 & 3\end{vmatrix} = 6 :

the $2\times2$ determinant is the signed area of the parallelogram of its columns. The axioms retell the geometry: adding a multiple of one column to the other is a shear, sliding the parallelogram parallel to a side without changing base or height (operation (1) of Theorem 22.3); scaling a column scales the area; swapping the columns flips the orientation, whence the sign, $\det(v, u) = -6$ . In $\R^3$ the same reading gives signed volumes, and $\abs{\det}$ becomes the universal volume-scaling factor of linear maps — the fact behind the change-of-variables formula for multiple integrals in the Year 2 volume.

Theorem 22.6 (Cofactor expansion)

Let $A \in \mathcal{M}_n(K)$ and $\Delta_{ij}$ the determinant of $A$ with row $i$ and column $j$ deleted. Then, for any fixed column $j$ (or row, by transposition):

\det A = \sum_{i=1}^{n} (-1)^{i+j}\, a_{ij}\, \Delta_{ij} .

Proof. Admitted at this level. ∎

Example 22.7

Expanding along the first column:

\begin{vmatrix} 2 & 1 & 0\\ 1 & 2 & 1\\ 0 & 1 & 2 \end{vmatrix} = 2\begin{vmatrix} 2 & 1\\ 1 & 2\end{vmatrix} - 1\begin{vmatrix} 1 & 0\\ 1 & 2\end{vmatrix} = 2 \times 3 - 2 = 4 .

Strategy: create zeros first (row/column operations), then expand along the emptiest line.

Example 22.8 (The cofactor inverse, once by hand)

For $A = \begin{pmatrix} 1 & 1 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1\end{pmatrix}$ : $\det A = 1(1) - 1(-1) + 0 = 2$ . The nine cofactors $(-1)^{i+j}\Delta_{ij}$ assemble into

\operatorname{Com}(A) = \begin{pmatrix} 1 & 1 & -1\\ -1 & 1 & 1\\ 1 & -1 & 1 \end{pmatrix}, \qquad A^{-1} = \frac{1}{\det A}\operatorname{Com}(A)^{\mathsf T} = \frac12\begin{pmatrix} 1 & -1 & 1\\ 1 & 1 & -1\\ -1 & 1 & 1 \end{pmatrix},

the formula quoted in Exercise 22.8. Check one row-column pair: (row $1$ of $A$ )(column $1$ of $A^{-1}$ ) $= \frac12(1 + 1 + 0) = 1$ , and against column $2$ : $\frac12(-1 + 1 + 0) = 0$ . Nine $2\times2$ determinants for one $3\times3$ inverse: already at this size, row reduction (Exercise 22.3) is cheaper — the cofactor formula’s value is theoretical (integrality in Exercise 22.8, differentiability of the inverse in later volumes), not computational.

Example 22.9 (The block-triangular rule, in size $4$ )

Claim: $\det\begin{pmatrix} M & N\\ 0 & P\end{pmatrix} = \det M\,\det P$ for $2\times2$ blocks. Clear the $N$ -block by column operations: adding to columns $3, 4$ suitable combinations of columns $1, 2$ removes $N$ when $M$ is invertible (solve $M\Lambda = -N$ for the combination coefficients $\Lambda$ ), leaving $\det\begin{pmatrix} M & 0\\ 0 & P\end{pmatrix}$ ; then cofactor expansion along the first column, twice, gives $\det M\det P$ for this block-diagonal shape. If $M$ is not invertible, its columns are linked, so the first two columns of the big matrix are linked (their bottom halves are zero): both sides vanish. The rule extends to any block sizes by the same two-case argument — and it is the engine of Exercise 22.10.

Example 22.10 (A $4 \times 4$ determinant, strategically)

\Delta = \begin{vmatrix} 1 & 2 & 3 & 4\\ 2 & 3 & 4 & 1\\ 3 & 4 & 1 & 2\\ 4 & 1 & 2 & 3 \end{vmatrix}.

Every row sums to $10$ : the operation $C_1 \leftarrow C_1 + C_2 + C_3 + C_4$ makes the first column constant, and factoring $10$ leaves ones. Then $L_i \leftarrow L_i - L_1$ ( $i \geq 2$ ) clears the first column:

\Delta = 10\begin{vmatrix} 1 & 2 & 3 & 4\\ 0 & 1 & 1 & -3\\ 0 & 2 & -2 & -2\\ 0 & -1 & -1 & -1 \end{vmatrix} = 10\begin{vmatrix} 1 & 1 & -3\\ 2 & -2 & -2\\ -1 & -1 & -1 \end{vmatrix} = 10 \times 16 = 160,

the last $3\times3$ determinant expanding along its first row: $1(2 - 2) - 1(-2 - 2) + (-3)(-2 - 2) = 0 + 4 + 12 = 16$ . Moral: one well-chosen operation (spotting the constant row sum) beats sixteen cofactors.

Method 22.11 (Choosing a determinant strategy)

Scan the matrix before computing anything.

Constant row or column sums: add everything into one line, factor the common value (Example 22.10, Exercise 22.7).
Repetitive structure: subtract neighboring rows or columns to create zeros; staircase patterns collapse toward triangular form, whose determinant is read on the diagonal.
Isolated zeros: expand along the emptiest line (Example 22.7); recursive families (tridiagonal, Exercise 22.6) yield recurrences this way.
A parameter: the determinant is a polynomial in it; find its roots by spotting the degenerate values (equal rows, proportional columns), then pin the polynomial down by degree and leading coefficient. For the matrix of Exercise 22.7: $m = 1$ gives three equal rows (rank $1$ , a double root), $m = -2$ makes the rows sum to zero (one more root); the determinant has degree $3$ in $m$ with leading term $-m^3$ (the anti-diagonal product $m\cdot m\cdot m$ , whose Sarrus sign is $-1$ ), so it must be $-(m+2)(m-1)^2$ — no expansion needed, and the two methods check each other.

Example 22.12 (Vandermonde determinant)

For scalars $x_1, \dots, x_n$ :

V(x_1, \dots, x_n) = \begin{vmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1}\\ \vdots & & & & \vdots\\ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \end{vmatrix} = \prod_{1 \leq i < j \leq n} (x_j - x_i) .

Proof sketch (detailed in Exercise 22.5): column operations $C_k \leftarrow C_k - x_1 C_{k-1}$ from the right clear the first row, and factoring each remaining row reduces to $V(x_2, \dots, x_n)$ . Nonzero iff the $x_i$ are pairwise distinct — the determinant behind Lagrange interpolation (Example 20.10).

22.2 Linear systems

Definition 22.13

A linear system of $n$ equations in $p$ unknowns is $AX = B$ with $A \in \mathcal{M}_{n,p}(K)$ , $B \in K^n$ ; it is homogeneous when $B = 0$ . Its solution set, when nonempty, is $X_0 + \ker A$ : a particular solution plus the general homogeneous solution — an affine subspace of dimension $p - \operatorname{rk} A$ (rank–nullity).

Example 22.14 (The affine structure, made visible)

Solve

\begin{cases} x + y + z = 3\\ x - y + 2z = 2 . \end{cases}

Subtracting the equations: $2y - z = 1$ , so $z = 2y - 1$ and $x = 3 - y - z = 4 - 3y$ . The solutions form the line

(x, y, z) = (4,\ 0,\ -1) + y\,(-3,\ 1,\ 2) \qquad (y \in \R):

the particular solution $X_0 = (4, 0, -1)$ (the choice $y = 0$ ) plus the kernel line $\ker A = \operatorname{Vect}(-3, 1, 2)$ of the associated homogeneous system — check: $(-3) + 1 + 2 = 0$ and $(-3) - 1 + 4 = 0$ . Geometrically, two non-parallel planes of $\R^3$ intersect along a line, and the dimension count $p - \operatorname{rk} A = 3 - 2 = 1$ knew it before we solved anything. Changing the particular solution (say $y = 1$ : $X_0' = (1, 1, 1)$ ) changes the description, not the line: an affine subspace has many origins and one direction.

Theorem 22.15 (Square Cramer systems)

If $A \in GL_n(K)$ , the system $AX = B$ has the unique solution $X = A^{-1}B$ , whose coordinates are

x_j = \frac{\det A_j}{\det A}, \qquad A_j = A \text{ with column } j \text{ replaced by } B .

Proof. Uniqueness and existence are the invertibility. For the formula: write $B = \sum_k x_k C_k$ (columns of $A$ ); then, by multilinearity and alternation,

\det A_j = \det\Bigl(C_1, \dots, \sum_k x_k C_k, \dots, C_n\Bigr) = \sum_k x_k \det(C_1, \dots, C_k, \dots, C_n) = x_j \det A ,

every term except $k = j$ having a repeated column. ∎

Example 22.16 (Cramer with a parameter, in full)

For $m \in \R$ , solve

\begin{cases} x + m y = 1\\ m x + y = 2 . \end{cases}

The determinant is $1 - m^2$ . Generic case $m \neq \pm1$ : Cramer gives

x = \frac{\begin{vmatrix} 1 & m\\ 2 & 1\end{vmatrix}}{1 - m^2} = \frac{1 - 2m}{1 - m^2}, \qquad y = \frac{\begin{vmatrix} 1 & 1\\ m & 2\end{vmatrix}}{1 - m^2} = \frac{2 - m}{1 - m^2},

one clean solution for each admissible $m$ (check at $m = 0$ : $(1, 2)$ , obviously right). Degenerate cases: at $m = 1$ the equations read $x + y = 1$ and $x + y = 2$ : incompatible; at $m = -1$ they read $x - y = 1$ and $-x + y = 2$ , i.e. $x - y = 1$ and $x - y = -2$ : incompatible again. The vanishing of the determinant announces that something degenerates, but never says what — empty or infinite must be decided by looking at the right-hand side. Note also how the formulas signal their own limits: as $m \to 1^{-}$ , $x = \frac{1 - 2m}{1 - m^2} \to -\infty$ ; the solution point runs away as the two lines become parallel.

Method 22.17 (Gaussian elimination on systems)

Row-reduce the augmented matrix $(A \mid B)$ to echelon form.

If a pivot appears in the last column ( $0 = 1$ line): no solution.
Otherwise, the unknowns split into pivot unknowns and free unknowns (parameters); back-substitution expresses the former in the latter: the solution set is an affine subspace of dimension $=$ number of free unknowns.

Cramer’s formulas are for theory and small systems; elimination is the practical algorithm.

Example 22.18 (A discussion with parameter)

For $m \in \R$ , consider

\begin{cases} x + y + mz = 1\\ x + my + z = 1\\ mx + y + z = 1 . \end{cases}

The matrix has determinant $-(m+2)(m-1)^2$ (computed in Exercise 22.7 by adding all columns to the first). For $m \neq 1, -2$ : unique solution $x = y = z = \frac{1}{m+2}$ (by symmetry). For $m = 1$ : one equation repeated thrice, a plane of solutions. For $m = -2$ : adding the three equations gives $0 = 3$ , no solution.

Remark 22.19 (Common pitfalls)

The determinant is not linear in the matrix: $\det(A + B) \neq \det A + \det B$ (already $\det(I_2 + I_2) = 4 \neq 2$ ); it is linear in each column separately, which is a different thing entirely. Scaling: $\det(\lambda A) = \lambda^n\det A$ , not $\lambda\det A$ — each of the $n$ columns is scaled. Row operations are not all free: $L_i \leftarrow L_i + \lambda L_j$ preserves the determinant, but a swap changes the sign and $L_i \leftarrow \lambda L_i$ multiplies it by $\lambda$ — bookkeeping errors here are the classic source of wrong signs in elimination-based computations. A zero determinant is the beginning, not the end: it says “rank $< n$ ” but not which rank; only further work (echelon form, or the minors of Exercise 22.12) locates it — cf. the case $m = 1$ vs $m = -2$ in Example 22.18. Cramer needs invertibility: when $\det A = 0$ the formulas $x_j = \det A_j/\det A$ are meaningless, and the system may perfectly well have (infinitely many) solutions. Only square matrices have determinants: for a rectangular system, elimination is the only tool.

Remark 22.20 (Where determinants go)

Three lives await this scalar. Geometric: $\abs{\det}$ is the area or volume scaling factor of the associated map — made precise for the plane in Chapter 23 and, as the Jacobian of a change of variables, in the multiple integrals of the Year 2 volume. Algebraic: $\det(A - \lambda I)$ , the characteristic polynomial, opens eigenvalue theory in Year 2 — the identity $A^2 - (\operatorname{tr} A)A + (\det A)I = 0$ of the Chapter 21 weekend problem is its first shadow. Analytic: determinants of special matrices (Vandermonde, Cauchy, Gram) decide when interpolation, decomposition and projection problems are well posed; the weekend problem below evaluates the first two families completely.

Remark 22.21 (Perspectives inside Book 3)

This chapter closes the linear-algebra spine of the volume, and its two remaining chapters cash the dividends. In Chapter 23: the Gram matrix $\bigl(\langle v_i, v_j\rangle\bigr)$ tests freeness by a determinant (Exercise 23.11), and the plane isometries split into rotations and reflections along the sign of their determinant — the classification of the weekend problem there runs on it. In Chapter 25: the Monge quantity $rt - s^2$ is the determinant of the symmetric matrix of second derivatives, and the normal equations of least squares are a Cramer system whose matrix is a Gram (hence moment) matrix — invertible precisely by the Vandermonde-flavored criteria established here. When those chapters assert “invertible” or “positive”, the receipts are in this one.

22.3 Exercises

Exercise 22.1 ★

Compute:

\begin{vmatrix} 3 & 1\\ 5 & 2 \end{vmatrix}, \qquad \begin{vmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\end{vmatrix}, \qquad \begin{vmatrix} 1 & 1 & 1\\ 1 & 2 & 4\\ 1 & 3 & 9\end{vmatrix}.

Solution

Solution of Exercise 22.1.

$3 \times 2 - 1 \times 5 = 1$ .

Second: $L_2 \leftarrow L_2 - L_1$ , $L_3 \leftarrow L_3 - L_2$ (on the original rows) give rows $(1,2,3), (3,3,3), (3,3,3)$ : two equal rows, determinant $0$ . (Sarrus confirms: $45 + 84 + 96 - 105 - 48 - 72 = 0$ .)

Third: it is Vandermonde with $x = 1, 2, 3$ (Example 22.12): $(2-1)(3-1)(3-2) = 2$ .

Exercise 22.2 ★

For which $\lambda \in \R$ is the family $\bigl((1, 1, \lambda), (1, \lambda, 1), (\lambda, 1, 1)\bigr)$ a basis of $\R^3$ ?

Solution

Solution of Exercise 22.2.

The determinant equals (add all columns to the first, factor) $(\lambda + 2)$ times

\begin{vmatrix} 1 & 1 & \lambda\\ 1 & \lambda & 1\\ 1 & 1 & 1 \end{vmatrix} = -(\lambda - 1)^2

(clear with $L_1 \leftarrow L_1 - L_3$ , $L_2 \leftarrow L_2 - L_3$ and expand), giving $\det = -(\lambda+2)(\lambda-1)^2$ . Basis $\iff \det \neq 0 \iff \lambda \notin \{1, -2\}$ .

Exercise 22.3 ★

Solve by Cramer’s rule:

\begin{cases} 2x + y = 5\\ 3x - 2y = 4 , \end{cases} \qquad\text{then}\qquad \begin{cases} x + y + z = 6\\ x - y + z = 2\\ 2x + y - z = 1 . \end{cases}

Solution

Solution of Exercise 22.3.

First system: $\det = -7$ ; $x = \frac{1}{-7}\begin{vmatrix} 5 & 1\\ 4 & -2\end{vmatrix} = \frac{-14}{-7} = 2$ , $y = \frac{1}{-7}\begin{vmatrix} 2 & 5\\ 3 & 4\end{vmatrix} = \frac{-7}{-7} = 1$ . Check: $2(2) + 1 = 5$ ; $3(2) - 2 = 4$ .

Second system: after $L_2 - L_1$ and $L_3 - 2L_1$ , the rows become $(1,1,1)$ , $(0,-2,0)$ , $(0,-1,-3)$ , so

\det A = \begin{vmatrix} 1&1&1\\ 1&-1&1\\ 2&1&-1\end{vmatrix} = 1 \times \begin{vmatrix} -2 & 0\\ -1 & -3\end{vmatrix} = 6 .

Cramer, replacing columns by $(6,2,1)^{\mathsf T}$ :

x = \frac{6}{6} = 1, \qquad y = \frac{12}{6} = 2, \qquad z = \frac{18}{6} = 3

(the numerators computed the same way). Check: $1 + 2 + 3 = 6$ ; $1 - 2 + 3 = 2$ ; $2 + 2 - 3 = 1$ .

Exercise 22.4 ★

Solve by Gaussian elimination, describing the solution set:

\begin{cases} x + 2y - z + t = 1\\ 2x + 4y + z - t = 5\\ x + 2y + 2z - 2t = 4 . \end{cases}

Solution

Solution of Exercise 22.4.

Reduce the augmented matrix: $L_2 \leftarrow L_2 - 2L_1$ , $L_3 \leftarrow L_3 - L_1$ :

\begin{pmatrix} 1 & 2 & -1 & 1 & 1\\ 0 & 0 & 3 & -3 & 3\\ 0 & 0 & 3 & -3 & 3 \end{pmatrix} \to \begin{pmatrix} 1 & 2 & -1 & 1 & 1\\ 0 & 0 & 1 & -1 & 1\\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}.

Pivot unknowns $x, z$ ; free unknowns $y, t$ . Back-substitution: $z = 1 + t$ , $x = 1 - 2y + z - t = 2 - 2y$ . Solution set:

\{(2 - 2y,\; y,\; 1 + t,\; t) : y, t \in \R\} = (2, 0, 1, 0) + \operatorname{Vect}\bigl((-2,1,0,0),\, (0,0,1,1)\bigr),

an affine plane (dimension $2 = 4 - \operatorname{rk} 2$ ) of $\R^4$ .

Exercise 22.5 ★★

Prove the Vandermonde formula of Example 22.12 by induction on $n$ , with the column operations $C_k \leftarrow C_k - x_1 C_{k-1}$ performed from $k = n$ down to $k = 2$ .

Solution

Solution of Exercise 22.5.

Induction; $n = 1$ is empty product $= 1$ . For the step, perform $C_k \leftarrow C_k - x_1 C_{k-1}$ for $k = n, n-1, \dots, 2$ (in this order, so each operation uses a not-yet-modified column). The first row becomes $(1, 0, \dots, 0)$ ; in row $i \geq 2$ , the $k$ -th entry becomes $x_i^{k-1} - x_1 x_i^{k-2} = x_i^{k-2}(x_i - x_1)$ . Expanding along the first row and factoring $(x_i - x_1)$ out of each row $i$ :

V(x_1, \dots, x_n) = \prod_{i=2}^{n} (x_i - x_1)\cdot V(x_2, \dots, x_n),

and the induction hypothesis completes the product $\prod_{i<j}(x_j - x_i)$ .

Exercise 22.6 ★★

(Tridiagonal) Let $D_n$ be the $n \times n$ determinant with $2$ on the diagonal, $1$ on the two adjacent diagonals, $0$ elsewhere. Expanding along the first row, prove $D_n = 2D_{n-1} - D_{n-2}$ and compute $D_n$ ( $D_1 = 2$ , $D_2 = 3$ ).

Solution

Solution of Exercise 22.6.

Expanding $D_n$ along the first row: $D_n = 2 D_{n-1} - 1\cdot\begin{vmatrix} 1 & \ast\\ 0 & D_{n-2}\text{-block} \end{vmatrix}$ ; the second determinant, expanded along its first column, is $D_{n-2}$ . So $D_n = 2D_{n-1} - D_{n-2}$ , i.e. $D_n - D_{n-1} = D_{n-1} - D_{n-2}$ : the differences are constant, equal to $D_2 - D_1 = 1$ . Hence $D_n = D_1 + (n - 1) = n + 1$ . (Check: $D_2 = 3$ , and the $3\times3$ case is Example 22.7: $D_3 = 4$ .)

Exercise 22.7 ★★

Complete Example 22.18: compute the determinant $\begin{vmatrix} 1 & 1 & m\\ 1 & m & 1\\ m & 1 & 1\end{vmatrix}$ by the operation $C_1 \leftarrow C_1 + C_2 + C_3$ , and carry out the full discussion of the system.

Solution

Solution of Exercise 22.7.

$C_1 \leftarrow C_1 + C_2 + C_3$ makes the first column constant $(m+2)$ ; factor it:

\det = (m+2)\begin{vmatrix} 1 & 1 & m\\ 1 & m & 1\\ 1 & 1 & 1 \end{vmatrix} \overset{L_1 - L_3,\ L_2 - L_3}{=} (m+2)\begin{vmatrix} 0 & 0 & m-1\\ 0 & m-1 & 0\\ 1 & 1 & 1 \end{vmatrix} = (m+2)\cdot\bigl(-(m-1)^2\bigr)

(expand along the first column: the single entry $1$ carries sign $+$ , and the remaining $2 \times 2$ determinant is $0 \cdot 0 - (m-1)(m-1) = -(m-1)^2$ ).

Discussion. $m \notin \{1, -2\}$ : Cramer system; by the symmetry of the equations, $x = y = z$ , and each equation gives $(m + 2)x = 1$ : unique solution $\bigl(\frac{1}{m+2}, \frac{1}{m+2}, \frac{1}{m+2}\bigr)$ . $m = 1$ : the three equations all read $x + y + z = 1$ : solutions form the affine plane $x + y + z = 1$ . $m = -2$ : summing the three equations gives $0 = 3$ : empty solution set.

Exercise 22.8 ★★

Let $A \in \mathcal{M}_n(\R)$ with integer entries. Prove that $A$ has an inverse with integer entries if and only if $\det A = \pm 1$ . (For the direct sense, take determinants; for the converse, admit — or prove for $n \leq 3$ via cofactors — that $A^{-1} = \frac{1}{\det A}\,\operatorname{Com}(A)^{\mathsf T}$ with integer cofactor matrix.)

Solution

Solution of Exercise 22.8.

( $\Rightarrow$ ) If $A^{-1}$ has integer entries: $\det A \cdot \det A^{-1} = 1$ with both determinants integers (sums of products of entries): two integers with product $1$ are both $\pm1$ .

( $\Leftarrow$ ) The cofactor formula $A^{-1} = \frac{1}{\det A}\operatorname{Com}(A)^{\mathsf T}$ (checked for $n \leq 3$ by direct expansion, admitted in general) has $\operatorname{Com}(A)$ with integer entries (each cofactor is an integer determinant); dividing by $\det A = \pm 1$ keeps integers.

Exercise 22.9 ★★★

Compute the $n \times n$ determinant of the matrix $aI + bJ$ (Exercise 21.9), i.e. with $a + b$ on the diagonal and $b$ elsewhere. (Add all columns to the first, factor, then clear.) Recover the invertibility condition $a \neq 0$ , $a + nb \neq 0$ .

Solution

Solution of Exercise 22.9.

Add all columns to the first: each entry of the new first column is $a + nb$ ; factor it out, so that the first column is all ones. Then the row operations $L_i \leftarrow L_i - L_1$ ( $i \geq 2$ ) clear every entry below the top-left $1$ and leave $a$ on the diagonal and $0$ elsewhere in those rows: the matrix is upper triangular with diagonal $(1, a, \dots, a)$ . Hence

\det(aI + bJ) = (a + nb)\, a^{\,n-1} ,

nonzero iff $a \neq 0$ and $a + nb \neq 0$ : the condition of Exercise 21.9.

Exercise 22.10 ★★★

Let $A, B \in \mathcal{M}_n(\R)$ . Prove that

\det\begin{pmatrix} A & B\\ B & A \end{pmatrix} = \det(A + B)\,\det(A - B),

by block column and row operations ( $C_1 \leftarrow C_1 + C_2$ , then $L_2 \leftarrow L_2 - L_1$ , in block form), assuming the natural block-triangular rule $\det\begin{pmatrix} M & N\\ 0 & P\end{pmatrix} = \det M \det P$ — proved for $2 \times 2$ blocks in Example 22.9.

Solution

Solution of Exercise 22.10.

Block operations (each a composition of the corresponding $n$ scalar operations, allowed by Theorem 22.3 (1)):

\begin{vmatrix} A & B\\ B & A\end{vmatrix} \overset{C_1 \leftarrow C_1 + C_2}{=} \begin{vmatrix} A + B & B\\ A + B & A\end{vmatrix} \overset{L_2 \leftarrow L_2 - L_1}{=} \begin{vmatrix} A + B & B\\ 0 & A - B\end{vmatrix} = \det(A+B)\,\det(A-B),

using the block-triangular rule for the last step.

Exercise 22.11 ★★

(Circulant of order $3$ ) Let $a, b, c \in \C$ and

\Delta = \begin{vmatrix} a & b & c\\ c & a & b\\ b & c & a \end{vmatrix}.

Prove that $\Delta = (a + b + c)(a^2 + b^2 + c^2 - ab - bc - ca)$ , and factor completely over $\C$ using $j = \eu^{2\iu\pi/3}$ :

\Delta = (a + b + c)(a + jb + j^2c)(a + j^2b + jc) .

(Start with $C_1 \leftarrow C_1 + C_2 + C_3$ ; for the complex form, note that the column $(1, j, j^2)^{\mathsf T}$ almost behaves like an eigenvector.)

Solution

Solution of Exercise 22.11.

$C_1 \leftarrow C_1 + C_2 + C_3$ makes the first column constant $(a + b + c)$ ; factor it out, then $L_2 \leftarrow L_2 - L_1$ , $L_3 \leftarrow L_3 - L_1$ :

\Delta = (a+b+c)\begin{vmatrix} 1 & b & c\\ 0 & a - b & b - c\\ 0 & c - b & a - c \end{vmatrix} = (a+b+c)\bigl[(a-b)(a-c) + (b-c)^2\bigr],

and expanding, $(a-b)(a-c) + (b-c)^2 = a^2 + b^2 + c^2 - ab - bc - ca$ . Over $\C$ , with $j^3 = 1$ and $1 + j + j^2 = 0$ :

\begin{align*} (a + jb + j^2c)(a + j^2b + jc) &= a^2 + b^2 + c^2 + (j + j^2)(ab + bc + ca)\\ &= a^2 + b^2 + c^2 - ab - bc - ca , \end{align*}

whence the complete factorization. (Structurally: the column $(1, j, j^2)^{\mathsf T}$ satisfies $M\,(1, j, j^2)^{\mathsf T} = (a + jb + j^2c)(1, j, j^2)^{\mathsf T}$ , and similarly for $j^2$ and $1$ : the three factors are the three “eigenvalues” of the circulant, a story systematized in the Year 2 volume.)

Exercise 22.12 ★★★

(Rank and minors) Let $A \in \mathcal{M}_{n,p}(K)$ . Prove that $\operatorname{rk} A$ equals the largest size $r$ of an invertible $r \times r$ submatrix of $A$ (a submatrix keeps the entries at the crossings of $r$ chosen rows and $r$ chosen columns). (If $\operatorname{rk} A = r$ , select $r$ free columns, then $r$ free rows of the resulting $n \times r$ block; conversely, an invertible submatrix forces the corresponding columns of $A$ to be free.)

Solution

Solution of Exercise 22.12.

Write $r = \operatorname{rk} A$ .

An invertible $r \times r$ submatrix exists. Choose $r$ free columns of $A$ and let $B \in \mathcal{M}_{n,r}$ be the matrix they form: $\operatorname{rk} B = r$ . Since row rank equals column rank (Theorem 21.13), $B$ has $r$ free rows; keeping those rows yields an $r \times r$ submatrix of $A$ of rank $r$ , i.e. invertible.

No larger one does. Let $S$ be an invertible $s \times s$ submatrix, taken from columns $j_1, \dots, j_s$ and rows $i_1, \dots, i_s$ of $A$ . If a combination $\sum_k \lambda_k C_{j_k} = 0$ of the corresponding full columns vanishes, then reading only the rows $i_1, \dots, i_s$ gives $\sum_k \lambda_k S_k = 0$ on the columns of $S$ , so all $\lambda_k = 0$ ( $S$ invertible): the columns $C_{j_1}, \dots, C_{j_s}$ of $A$ are free, and $s \leq \operatorname{rk} A = r$ .

Hence $\operatorname{rk} A$ is exactly the largest size of an invertible submatrix.

22.4 Problem: Cauchy’s double alternant

Problem 22.1

Two determinants rule the applications of this chapter: the Vandermonde determinant, evaluated in Exercise 22.5, and the Cauchy determinant $\det\bigl(\frac{1}{a_i + b_j}\bigr)$ , evaluated here. Around them this problem collects the alternant toolbox: polynomial column tricks, interpolation by Cramer, the Hilbert matrix, the discriminant of a cubic, and the method of alternating polynomials. Throughout, $V(x_1, \dots, x_n) = \prod_{i < j}(x_j - x_i)$ denotes the Vandermonde value.

Part I — The Vandermonde toolbox.

Compute $V(1, 2, 3, 4)$ , and recall why interpolation at $n$ pairwise distinct nodes is a Cramer system.
(Polynomial alternant) Let $P_0, \dots, P_{n-1}$ be monic with $\deg P_k = k$ . Prove

$\det\bigl(P_{j-1}(x_i)\bigr)_{1 \leq i, j \leq n} = V(x_1, \dots, x_n) :$

column operations replace each power column by any monic staircase, for free.
Apply question 2 to the binomial polynomials $B_k = \frac{X(X-1)\cdots(X-k+1)}{k!}$ : prove that for integers $m_1 < m_2 < \dots < m_n$ ,

$\frac{V(m_1, \dots, m_n)}{0!\,1!\,2!\cdots(n-1)!} \in \N :$

the product of all pairwise differences of $n$ integers is divisible by the superfactorial $0!\,1!\cdots(n-1)!$ .
Prove $\det\bigl(x_i^{\,j}\bigr)_{1 \leq i, j \leq n} = x_1 x_2 \cdots x_n\, V(x_1, \dots, x_n)$ (powers now starting at $1$ ).
(Moment matrix) Let $S = \bigl(p_{i+j-2}\bigr)_{1 \leq i, j \leq n}$ where $p_k = x_1^k + \dots + x_n^k$ . Prove that $S = W^{\mathsf T} W$ for the matrix $W = (x_i^{\,j-1})_{ij}$ , deduce

$\det S = V(x_1, \dots, x_n)^2 ,$

and conclude: $n$ real numbers are pairwise distinct if and only if their moment matrix is invertible, and $\det S \geq 0$ always.

Part II — Interpolation revisited. Nodes $x_1 < \dots < x_n$ , values $y_1, \dots, y_n$ .

Write the conditions “ $P = c_0 + c_1X + \dots + c_{n-1}X^{n-1}$ interpolates” as a linear system in the $c_k$ with matrix $W$ , and recover from $\det W = V \neq 0$ the existence and uniqueness of the interpolant (compare the two earlier proofs, Theorem 8.23 and Example 20.10).
By Cramer’s rule and cofactor expansion of the relevant determinant along its last column, prove that the leading coefficient of the interpolant is

$c_{n-1} = \sum_{i=1}^{n} \frac{y_i}{\prod_{j \neq i}(x_i - x_j)} .$
(Confluent Vandermonde) Compute

$\begin{vmatrix} 1 & x_1 & x_1^2\\ 0 & 1 & 2x_1\\ 1 & x_2 & x_2^2 \end{vmatrix} = (x_2 - x_1)^2 ,$

and interpret: the data $\bigl(P(x_1), P'(x_1), P(x_2)\bigr)$ determine a unique $P \in \R_2[X]$ when $x_1 \neq x_2$ (Hermite interpolation).
Find the unique $P \in \R_2[X]$ with $P(0) = 1$ , $P'(0) = 0$ , $P(1) = 2$ , and check your answer against question 8.

Part III — The Cauchy determinant. Let $a_1, \dots, a_n$ and $b_1, \dots, b_n$ be scalars with $a_i + b_j \neq 0$ for all $i, j$ , and

C_n = \det\Bigl(\frac{1}{a_i + b_j}\Bigr)_{1 \leq i, j \leq n} .

Compute $C_2$ by hand and put it in the form “products of differences over products of sums”.
For $n \geq 2$ , perform $L_i \leftarrow L_i - L_n$ ( $i < n$ ) and factor rows and columns to prove

$C_n = \frac{\prod_{i<n}(a_n - a_i)}{\prod_{j}(a_n + b_j)}\;\det M,$

where $M$ agrees with the Cauchy matrix on rows $i < n$ and has last row $(1, 1, \dots, 1)$ .
Perform $C_j \leftarrow C_j - C_n$ ( $j < n$ ) on $M$ , factor again, and conclude by induction Cauchy’s double alternant:

$C_n = \frac{\prod_{1 \leq i < j \leq n}(a_j - a_i)(b_j - b_i)}{\prod_{i, j}(a_i + b_j)} .$
Deduce the invertibility criterion (the $a_i$ pairwise distinct and the $b_j$ pairwise distinct). For the Hilbert matrix $H_n = \bigl(\frac{1}{i + j - 1}\bigr)$ : compute $\det H_2$ and $\det H_3$ from the formula, and verify that $H_2^{-1}$ has integer entries.
Show that for pairwise distinct $b_j$ and any right-hand side, the system $\sum_j \frac{c_j}{a_i + b_j} = y_i$ ( $i = 1, \dots, n$ ) has a unique solution, and relate this to the existence and uniqueness of partial fraction decompositions with simple poles (Theorem 9.5).

Part IV — The discriminant of a cubic. Let $\lambda_1, \lambda_2, \lambda_3$ be the roots (in $\C$ ) of $X^3 + pX + q$ , and $p_k = \lambda_1^k + \lambda_2^k + \lambda_3^k$ .

Using $\lambda^3 = -p\lambda - q$ at each root and Vieta ( $p_1 = 0$ ), compute $p_2 = -2p$ , $p_3 = -3q$ , and $p_4 = 2p^2$ .
With question 5 (over $\C$ , keeping $\det S = V^2$ ), compute

$\operatorname{disc} = V(\lambda_1, \lambda_2, \lambda_3)^2 = \begin{vmatrix} 3 & 0 & -2p\\ 0 & -2p & -3q\\ -2p & -3q & 2p^2 \end{vmatrix} = -4p^3 - 27q^2 .$
Deduce: $X^3 + pX + q$ has a repeated root if and only if $4p^3 + 27q^2 = 0$ ; check on $X^3 - 3X + 2 = (X - 1)^2(X + 2)$ .
Suppose $p, q$ real. Prove that the cubic has three distinct real roots if and only if $\operatorname{disc} > 0$ , and one real plus two nonreal conjugate roots if and only if $\operatorname{disc} < 0$ . (If $\lambda_3 = \conj{\lambda_2} \neq \lambda_2$ and $\lambda_1 \in \R$ , show $V$ is purely imaginary.)

Part V — Dividends, and the alternating method.

For $0 < a_1 < a_2 < \dots < a_n$ , show $\det\bigl(\frac{1}{a_i + a_j}\bigr) > 0$ .
Compute $\det\bigl(\binom{m_i}{j-1}\bigr)_{1 \leq i, j \leq 3}$ for $(m_1, m_2, m_3) = (2, 4, 7)$ , first by questions 2–3, then by direct expansion.
Let $\lambda_1, \dots, \lambda_n$ be pairwise distinct and nonzero. Using an invertible Vandermonde matrix, prove again that the geometric sequences $\bigl((\lambda_i^{\,k})_{k \geq 0}\bigr)_{1 \leq i \leq n}$ form a free family of the space of sequences.
Compute $\det\bigl(\frac{1}{i + j}\bigr)_{1 \leq i, j \leq 3}$ from the double alternant.
(Alternating polynomials) Call a polynomial $F$ in $x_1, \dots, x_n$ alternating when swapping any two variables changes its sign. Show that an alternating $F$ vanishes whenever $x_i = x_j$ ( $i \neq j$ ), and deduce — one variable at a time, by the factor theorem — that $F$ is divisible by $\prod_{i<j}(x_j - x_i)$ .
Use question 23 to reprove the Vandermonde formula with no induction: the determinant $\det(x_i^{\,j-1})$ is an alternating polynomial of total degree $\binom n2$ , hence a constant multiple of $\prod_{i<j}(x_j - x_i)$ ; identify the constant by comparing one monomial.
Synthesis, in four sentences: what single property of the determinant (which axiom) generates all the factorizations of this problem; why the moment-matrix identity of question 5 turns a statement about complex distinctness into a computable real sign test; which two classical matrices were completely evaluated here and which linear problems they govern; and how the alternating method of questions 23–24 explains, in one stroke, why $\prod_{i<j}(x_j - x_i)$ keeps appearing. Name the theorem of Part III.

Solution

Solution of Problem 22.1.

1. $V(1,2,3,4) = (2-1)(3-1)(4-1)(3-2)(4-2)(4-3) = 1 \cdot 2\cdot 3\cdot 1\cdot 2\cdot 1 = 12$ . Interpolation at distinct nodes asks for the coefficients of $P$ solving $W c = y$ with $W = (x_i^{\,j-1})$ , and $\det W = V \neq 0$ : a Cramer system.

2. Work through the columns from left to right. $C_1$ is the constant column $P_0(x_i) = 1$ ( $P_0$ monic of degree $0$ ). Assume columns $1, \dots, j-1$ have already been reduced to the pure powers $1, x_i, \dots, x_i^{\,j-2}$ . Since $P_{j-1} = X^{j-1} + \sum_{k < j-1}\alpha_k X^k$ , subtracting from $C_j$ the combination $\sum_k \alpha_k\,(\text{column of } x_i^k)$ — an operation that does not change the determinant — leaves the pure power column $x_i^{\,j-1}$ . After the last column the matrix is the Vandermonde matrix: $\det = V(x_1, \dots, x_n)$ .

3. The polynomials $(j-1)!\,B_{j-1}$ are monic of degree $j - 1$ , so question 2 gives

\det\bigl(B_{j-1}(m_i)\bigr) = \frac{V(m_1, \dots, m_n)}{0!\,1!\cdots(n-1)!} .

The left side is the determinant of a matrix with integer entries ( $B_k$ is integer-valued on $\Z$ : questions 16–17 of the weekend problem Problem 18.1), hence an integer; and it is positive since $V(m_1, \dots, m_n) > 0$ for $m_1 < \dots < m_n$ . So the superfactorial divides the product of all pairwise differences.

4. Factor $x_i$ out of each row $i$ : $\det(x_i^{\,j})_{j = 1..n} = x_1\cdots x_n\, \det(x_i^{\,j-1}) = x_1\cdots x_n\,V$ .

5. $(W^{\mathsf T}W)_{ij} = \sum_k x_k^{\,i-1} x_k^{\,j-1} = p_{i+j-2}$ : $S = W^{\mathsf T}W$ . Hence $\det S = \det(W^{\mathsf T})\det W = V^2$ (Theorem 22.3 (2),(4)). For real $x_i$ : $\det S = V^2 \geq 0$ , and $S$ is invertible iff $V \neq 0$ iff the $x_i$ are pairwise distinct — a sign-definite test computable from the power sums alone.

6. The interpolation conditions $\sum_{k} c_k\,x_i^{\,k} = y_i$ form the system $Wc = y$ ; $\det W = V \neq 0$ gives existence and uniqueness at once. This is the third proof in the book: explicit formula in Theorem 8.23, kernel argument in Example 20.10, Cramer here.

7. Cramer: $c_{n-1} = \det W'/\det W$ where $W'$ is $W$ with its last column replaced by $y$ . Expanding $\det W'$ along that column:

\det W' = \sum_{i=1}^n (-1)^{i+n} y_i\,V(x_1, \dots, \widehat{x_i}, \dots, x_n) .

Now $V = V(\setminus i)\cdot\prod_{j<i}(x_i - x_j)\prod_{j>i} (x_j - x_i)$ , and converting the second product costs $(-1)^{n-i}$ :

(-1)^{i+n}\,\frac{V(\setminus i)}{V} = \frac{(-1)^{i+n}(-1)^{n-i}}{\prod_{j\neq i}(x_i - x_j)} = \frac{1}{\prod_{j\neq i}(x_i - x_j)} ,

whence $c_{n-1} = \sum_i y_i/\prod_{j \neq i}(x_i - x_j)$ — the divided-difference formula again.

8. $L_3 \leftarrow L_3 - L_1$ gives the rows $(1, x_1, x_1^2)$ , $(0, 1, 2x_1)$ , $(0,\ x_2 - x_1,\ (x_2-x_1)(x_2+x_1))$ ; expanding along the first column and factoring $(x_2 - x_1)$ :

(x_2 - x_1)\begin{vmatrix} 1 & 2x_1\\ 1 & x_2 + x_1 \end{vmatrix} = (x_2 - x_1)(x_2 - x_1) = (x_2 - x_1)^2 .

Nonzero for $x_1 \neq x_2$ : the linear system expressing $P(x_1) = u$ , $P'(x_1) = v$ , $P(x_2) = w$ on the coefficients of $P \in \R_2[X]$ is Cramer — Hermite interpolation with a doubled node is well posed.

9. $P = a + bX + cX^2$ with $a = P(0) = 1$ , $b = P'(0) = 0$ , $a + b + c = P(1) = 2$ : $c = 1$ , so $P = 1 + X^2$ , unique. Consistency: here $x_1 = 0$ , $x_2 = 1$ and the determinant of question 8 is $(1 - 0)^2 = 1 \neq 0$ .

10. Direct computation:

C_2 = \frac{1}{(a_1+b_1)(a_2+b_2)} - \frac{1}{(a_1+b_2)(a_2+b_1)} = \frac{(a_1+b_2)(a_2+b_1) - (a_1+b_1)(a_2+b_2)} {\prod_{i,j}(a_i+b_j)} ,

and the numerator expands to $a_1b_1 + a_2b_2 - a_1b_2 - a_2b_1 = (a_2 - a_1)(b_2 - b_1)$ : differences over sums.

11. For $i < n$ , the new entry of row $i$ is

\frac{1}{a_i + b_j} - \frac{1}{a_n + b_j} = \frac{a_n - a_i}{(a_i + b_j)(a_n + b_j)} .

Factor $(a_n - a_i)$ out of each row $i < n$ , then $\frac1{a_n + b_j}$ out of each column $j$ : what remains has entries $\frac1{a_i + b_j}$ in rows $i < n$ and constant $1$ in row $n$ — the matrix $M$ , with the announced prefactor.

12. On $M$ , for $j < n$ the operation $C_j \leftarrow C_j - C_n$ turns row $n$ into $(0, \dots, 0, 1)$ and, in row $i < n$ ,

\frac{1}{a_i + b_j} - \frac{1}{a_i + b_n} = \frac{b_n - b_j}{(a_i + b_j)(a_i + b_n)} .

Factor $(b_n - b_j)$ from each column $j < n$ and $\frac1{a_i + b_n}$ from each row $i < n$ , then expand along the last row (sign $(-1)^{n+n} = +1$ ): the remaining determinant is $C_{n-1}$ . Collecting the factors of questions 11–12:

C_n = \frac{\prod_{i<n}(a_n - a_i)\,\prod_{j<n}(b_n - b_j)} {\prod_{j}(a_n + b_j)\,\prod_{i<n}(a_i + b_n)}\;C_{n-1},

and the induction (base $C_1 = \frac1{a_1+b_1}$ ) assembles exactly Cauchy’s double alternant: the factors $(a_j - a_i)(b_j - b_i)$ for all pairs, over all sums $(a_i + b_j)$ .

13. The formula vanishes iff some $a_j = a_i$ or $b_j = b_i$ : the Cauchy matrix is invertible iff both families are pairwise distinct. Hilbert: $a_i = i$ , $b_j = j - 1$ . For $n = 2$ : numerator $(2-1)(1-0) = 1$ , denominator $1\cdot2\cdot2\cdot3 = 12$ : $\det H_2 = \frac1{12}$ . For $n = 3$ : numerator $\bigl[(1)(2)(1)\bigr]^2 = 4$ , denominator $(1\cdot2\cdot3) (2\cdot3\cdot4)(3\cdot4\cdot5) = 6\cdot24\cdot60 = 8640$ : $\det H_3 = \frac{4}{8640} = \frac1{2160}$ . Inverse for $n = 2$ :

H_2^{-1} = 12\begin{pmatrix} \frac13 & -\frac12\\[2pt] -\frac12 & 1\end{pmatrix} = \begin{pmatrix} 4 & -6\\ -6 & 12 \end{pmatrix},

all integers (a phenomenon true for every $n$ ).

14. The matrix of the system is the Cauchy matrix, invertible by question 13 when the $b_j$ (and the $a_i$ ) are pairwise distinct: unique solution. Interpretation: a rational function $R = \sum_j \frac{c_j}{X + b_j}$ with simple poles is determined by $n$ of its values $R(a_1), \dots, R(a_n)$ , and conversely any such data sheet is realized exactly once — the sampling counterpart of the partial-fraction existence and uniqueness theorem (Theorem 9.5).

15. Vieta for $X^3 + pX + q$ : $\lambda_1 + \lambda_2 + \lambda_3 = 0$ , $\sum_{i<j}\lambda_i\lambda_j = p$ , so $p_1 = 0$ and $p_2 = p_1^2 - 2p = -2p$ . Each root satisfies $\lambda^3 = -p\lambda - q$ ; summing: $p_3 = -p\,p_1 - 3q = -3q$ . Multiplying by $\lambda$ and summing: $p_4 = -p\,p_2 - q\,p_1 = 2p^2$ .

16. By question 5 (the identity $S = W^{\mathsf T}W$ and $\det S = V^2$ are valid over $\C$ ),

V^2 = \begin{vmatrix} 3 & 0 & -2p\\ 0 & -2p & -3q\\ -2p & -3q & 2p^2 \end{vmatrix} = 3\bigl(-4p^3 - 9q^2\bigr) + (-2p)\bigl(0 - 4p^2\bigr) = -4p^3 - 27q^2 ,

expanding along the first row.

17. A repeated root means two equal $\lambda_i$ , i.e. $V = 0$ , i.e. $\operatorname{disc} = -4p^3 - 27q^2 = 0$ . For $X^3 - 3X + 2$ : $4(-3)^3 + 27\cdot4 = -108 + 108 = 0$ , matching the double root $1$ of $(X-1)^2(X+2)$ .

18. The nonreal roots of a real cubic come in conjugate pairs, so exactly two cases occur when $\operatorname{disc} \neq 0$ . Three distinct real roots: $V$ is real and nonzero, so $\operatorname{disc} = V^2 > 0$ . One real root $\lambda_1$ and $\lambda_3 = \conj{\lambda_2} \notin \R$ : then

(\lambda_2 - \lambda_1)(\lambda_3 - \lambda_1) = \abs{\lambda_2 - \lambda_1}^2 > 0, \qquad \lambda_3 - \lambda_2 = -2\iu\,\operatorname{Im}\lambda_2 \neq 0,

so $V$ is a nonzero purely imaginary number and $\operatorname{disc} = V^2 < 0$ . The two signs characterize the two cases.

19. Take $b_i = a_i$ in the double alternant: the numerator is $\prod_{i<j}(a_j - a_i)^2 > 0$ and the denominator $\prod_{i,j}(a_i + a_j) > 0$ (all entries positive): the determinant is positive. (In later language: the kernel $\frac1{x+y}$ is positive definite.)

20. By questions 2–3, the determinant equals $V(2,4,7)/(0!\,1!\,2!) = \frac{(4-2)(7-2)(7-4)}{2} = \frac{30}{2} = 15$ . Directly, the matrix is

\begin{pmatrix} 1 & 2 & 1\\ 1 & 4 & 6\\ 1 & 7 & 21 \end{pmatrix}, \qquad \det = (84 - 42) - 2(21 - 6) + (7 - 4) = 42 - 30 + 3 = 15 .

21. Suppose $\sum_i c_i\,(\lambda_i^{\,k})_{k} = 0$ as a sequence. Reading off $k = 0, 1, \dots, n-1$ gives $W^{\mathsf T}c = 0$ with $W = (\lambda_i^{\,j-1})$ invertible ( $\det = V \neq 0$ , distinct $\lambda_i$ ): $c = 0$ . The geometric sequences are free.

22. $a = b = (1, 2, 3)$ : numerator $\bigl[(2-1)(3-1) (3-2)\bigr]^2 = 4$ ; denominator $\prod_{i,j}(i + j) = (2\cdot3\cdot4)(3\cdot4\cdot5)(4\cdot5\cdot6) = 24\cdot60\cdot120 = 172800$ . Hence $\det\bigl(\frac1{i+j}\bigr) = \frac{4}{172800} = \frac1{43200}$ .

23. If $x_i = x_j$ , the swap of the two variables fixes the point but must change the sign of $F$ : $F = -F$ , so $F = 0$ there. Divisibility: view $F$ as a polynomial in the single variable $x_n$ with coefficients in the other variables; it vanishes at the $n - 1$ “values” $x_1, \dots, x_{n-1}$ , so repeated factoring (Theorem 8.7) gives $F = \prod_{i<n}(x_n - x_i)\cdot G$ with $G$ polynomial. The prefactor is invariant under swaps of two indices $i, j < n$ , so $G$ is alternating in $x_1, \dots, x_{n-1}$ , and induction completes: $\prod_{i<j}(x_j - x_i)$ divides $F$ .

24. $D = \det(x_i^{\,j-1})$ is a polynomial in the $x_i$ ; swapping two variables swaps two rows, so $D$ is alternating, and by question 23, $D = c\,\prod_{i<j}(x_j - x_i)$ for some polynomial $c$ . Total degrees: $D$ has degree $\leq 0 + 1 + \dots + (n-1) = \binom n2$ , the product has degree exactly $\binom n2$ : $c$ is a constant. The monomial $x_2\,x_3^2\cdots x_n^{\,n-1}$ has coefficient $1$ in $D$ (diagonal product) and $1$ in the product (choose the larger-index variable in every factor): $c = 1$ , and Vandermonde’s formula falls out with no induction.

25. (i) Alternation — the axiom “two equal columns kill the determinant” — is the engine: it produced every factor $(x_j - x_i)$ , $(a_j - a_i)$ , $(b_j - b_i)$ in the problem. (ii) The identity $\det S = V^2$ replaces the individually complex, unreachable roots by their power sums, which are real polynomials in the coefficients, so distinctness becomes the sign of a computable real number. (iii) The Vandermonde determinant governs polynomial interpolation, the Cauchy determinant governs partial fractions and sampled rational functions (with the Hilbert matrix as its most famous special case). (iv) Any alternating polynomial is divisible by $\prod_{i<j}(x_j - x_i)$ , and a degree count then pins such a polynomial down up to a constant — which is why this product keeps reappearing wherever a determinant vanishes on coincidences. The theorem of Part III is Cauchy’s double alternant.

Terms defined in this chapter

system

See all 395 terms in the glossary