3.2: Determinants and Matrix Inverses

In this section, several theorems about determinants are derived. One consequence of these theorems is that a square matrix \(A\) is invertible if and only if \(\det A \neq 0\). Moreover, determinants are used to give a formula for \(A^{-1}\) which, in turn, yields a formula (called Cramer’s rule) for the solution of any system of linear equations with an invertible coefficient matrix.

We begin with a remarkable theorem (due to Cauchy in 1812) about the determinant of a product of matrices. The proof is given at the end of this section.

Product Theorem008196 If \(A\) and \(B\) are \(n \times n\) matrices, then \(\det (AB) = \det A \det B\).

The complexity of matrix multiplication makes the product theorem quite unexpected. Here is an example where it reveals an important numerical identity.

008202 If \(A = \left[ \begin{array}{rr} a & b \\ -b & a \end{array} \right]\) and \(B = \left[ \begin{array}{rr} c & d \\ -d & c \end{array} \right]\) then \(AB = \left[ \begin{array}{cc} ac-bd & ad+bc \\ -(ad+bc) & ac-bd \end{array} \right]\).

Hence \(\det A \det B = \det (AB)\) gives the identity

\[(a^2 + b^2)(c^2+d^2) = (ac-bd)^2 + (ad+bc)^2 \nonumber \]

Theorem [thm:008196] extends easily to \(\det (ABC) = \det A \det B \det C\). In fact, induction gives

\[\det (A_1A_2 \cdots A_{k-1}A_k) = \det A_1 \det A_2 \cdots \det A_{k-1} \det A_k \nonumber \]

for any square matrices \(A_1, \dots, A_k\) of the same size. In particular, if each \(A_i = A\), we obtain

\[\det (A^k) = (det A)^k, \mbox{ for any } k\geq 1 \nonumber \]

We can now give the invertibility condition.

008217 An \(n \times n\) matrix \(A\) is invertible if and only if \(\det A \neq 0\). When this is the case, \(\det (A^{-1}) = \frac{1}{\det A}\)

If \(A\) is invertible, then \(AA^{-1}=I\); so the product theorem gives

\[1 = \det I = \det (AA^{-1}) = \det A \det A^{-1} \nonumber \]

Hence, \(\det A \neq 0\) and also \(\det A^{-1} = \frac{1}{\det A}\).

Conversely, if \(\det A \neq 0\), we show that \(A\) can be carried to \(I\) by elementary row operations (and invoke Theorem [thm:004553]). Certainly, \(A\) can be carried to its reduced row-echelon form \(R\), so \(R = E_k \cdots E_2E_1A\) where the \(E_i\) are elementary matrices (Theorem [thm:005294]). Hence the product theorem gives

\[\det R = \det E_k \cdots \det E_2 \det E_1 \det A \nonumber \]

Since \(\det E \neq 0\) for all elementary matrices \(E\), this shows \(\det R \neq 0\). In particular, \(R\) has no row of zeros, so \(R = I\) because \(R\) is square and reduced row-echelon. This is what we wanted.

008234 For which values of \(c\) does \(A = \left[ \begin{array}{rcr} 1 & 0 & -c \\ -1 & 3 & 1 \\ 0 & 2c & -4 \end{array} \right]\) have an inverse?

Compute \(\det A\) by first adding \(c\) times column 1 to column 3 and then expanding along row 1.

\[\det A = \det \left[ \begin{array}{rcr} 1 & 0 & -c \\ -1 & 3 & 1 \\ 0 & 2c & -4 \end{array} \right] = \det \left[ \begin{array}{rcc} 1 & 0 & 0 \\ -1 & 3 & 1-c \\ 0 & 2c & -4 \end{array} \right] = 2(c+2)(c-3) \nonumber \]

Hence, \(\det A = 0\) if \(c = -2\) or \(c = 3\), and \(A\) has an inverse if \(c \neq -2\) and \(c \neq 3\).

008243 If a product \(A_1A_2\cdots A_k\) of square matrices is invertible, show that each \(A_i\) is invertible.

We have \(\det A_1\det A_2\cdots \det A_k = \det (A_1A_2\cdots A_k)\) by the product theorem, and \(\det (A_1A_2\cdots A_k) \neq 0\) by Theorem [thm:008217] because \(A_1A_2\cdots A_k\) is invertible. Hence

\[\det A_1 \det A_2 \cdots \det A_k \neq 0 \nonumber \]

so \(\det A_i \neq 0\) for each \(i\). This shows that each \(A_i\) is invertible, again by Theorem [thm:008217].

008268 If \(A\) is any square matrix, \(\det A^T = \det A\).

Consider first the case of an elementary matrix \(E\). If \(E\) is of type I or II, then \(E^T = E\); so certainly \(\det E^T = \det E\). If \(E\) is of type III, then \(E^T\) is also of type III; so \(\det E^T = 1 = \det E\) by Theorem [thm:007779]. Hence, \(\det E^T = \det E\) for every elementary matrix \(E\).

Now let \(A\) be any square matrix. If \(A\) is not invertible, then neither is \(A^T\); so \(\det A^T = 0 = \det A\) by Theorem [thm:008217]. On the other hand, if \(A\) is invertible, then \(A = E_k \cdots E_2E_1\), where the \(E_i\) are elementary matrices (Theorem [thm:005336]). Hence, \(A^T = E^T_1E^T_2 \cdots E^T_k\) so the product theorem gives

\[\begin{aligned} \det A^T = \det E^T_1 \det E^T_2 \cdots \det E^T_k & = \det E_1 \det E_2 \cdots \det E_k \\ &= \det E_k \cdots \det E_2 \det E_1 \\ &= \det A\end{aligned} \nonumber \]

This completes the proof.

008291 If \(\det A = 2\) and \(\det B = 5\), calculate \(\det (A^3 B^{-1}A^TB^2)\).

We use several of the facts just derived.

\[\begin{aligned} \det (A^3 B^{-1}A^TB^2) &= \det (A^3) \det (B^{-1}) \det (A^T) \det (B^2)\\ &= (\det A)^3 \frac{1}{\det B} \det A (\det B)^2 \\ &= 2^3 \cdot \frac{1}{5} \cdot 2 \cdot 5^2 \\ &= 80\end{aligned} \nonumber \]

008302 A square matrix is called orthogonal if \(A^{-1} = A^T\). What are the possible values of \(\det A\) if \(A\) is orthogonal?

If \(A\) is orthogonal, we have \(I = AA^T\). Take determinants to obtain

\[1 = \det I = \det (AA^T) = \det A \det A^T = (\det A)^2 \nonumber \]

Since \(\det A\) is a number, this means \(\det A = \pm 1\).

Hence Theorems [thm:006021] and [thm:006096] imply that rotation about the origin and reflection about a line through the origin in \(\mathbb{R}^2\) have orthogonal matrices with determinants \(1\) and \(-1\) respectively. In fact they are the only such transformations of \(\mathbb{R}^2\). We have more to say about this in Section [sec:8_2].

Adjugates

In Section [sec:2_4] we defined the adjugate of a 2 \(\times\) 2 matrix \(A = \left[ \begin{array}{rr} a & b \\ c & d \end{array} \right]\) to be \(\text{adj} (A) = \left[ \begin{array}{rr} d & -b \\ -c & a \end{array} \right]\). Then we verified that \(A (\text{adj} A) = (\det A)I = (\text{adj} A)A\) and hence that, if \(\det A \neq 0\), \(A^{-1} = \frac{1}{\det A} \text{adj} A\). We are now able to define the adjugate of an arbitrary square matrix and to show that this formula for the inverse remains valid (when the inverse exists).

Recall that the \((i, j)\)-cofactor \(c_{ij}(A)\) of a square matrix \(A\) is a number defined for each position \((i, j)\) in the matrix. If \(A\) is a square matrix, the cofactor matrix of \(A\) is defined to be the matrix \(\left[ c_{ij}(A)\right]\) whose \((i, j)\)-entry is the \((i, j)\)-cofactor of \(A\).

Adjugate of a Matrix008326 The adjugate of \(A\), denoted \(\text{adj} (A)\), is the transpose of this cofactor matrix; in symbols,

\[\text{adj } (A) = \left[ c_{ij}(A) \right]^T \nonumber \]

This agrees with the earlier definition for a \(2 \times 2\) matrix \(A\) as the reader can verify.

008331 Compute the adjugate of \(A = \left[ \begin{array}{rrr} 1 & 3 & -2 \\ 0 & 1 & 5 \\ -2 & -6 & 7 \end{array}\right]\) and calculate \(A (\text{adj} A)\) and \((\text{adj} A)A\).

We first find the cofactor matrix.

\[\begin{aligned} \left[ \begin{array}{rrr} c_{11}(A) & c_{12}(A) & c_{13}(A) \\ c_{21}(A) & c_{22}(A) & c_{23}(A) \\ c_{31}(A) & c_{32}(A) & c_{33}(A) \end{array}\right] &= \left[ \begin{array}{ccc} \left| \begin{array}{rr} 1 & 5 \\ -6 & 7 \end{array}\right| & -\left| \begin{array}{rr} 0 & 5 \\ -2 & 7 \end{array}\right| & \left| \begin{array}{rr} 0 & 1 \\ -2 & -6 \end{array}\right| \\ & & \\ -\left| \begin{array}{rr} 3 & -2 \\ -6 & 7 \end{array}\right| & \left| \begin{array}{rr} 1 & -2 \\ -2 & 7 \end{array}\right| & -\left| \begin{array}{rr} 1 & 3 \\ -2 & -6 \end{array}\right| \\ & & \\ \left| \begin{array}{rr} 3 & -2 \\ 1 & 5 \end{array}\right| & -\left| \begin{array}{rr} 1 & -2 \\ 0 & 5 \end{array}\right| & \left| \begin{array}{rr} 1 & 3 \\ 0 & 1 \end{array}\right| \end{array}\right] \\ &= \left[ \begin{array}{rrr} 37 & -10 & 2 \\ -9 & 3 & 0 \\ 17 & -5 & 1 \end{array}\right]\end{aligned} \nonumber \]

Then the adjugate of \(A\) is the transpose of this cofactor matrix.

\[\text{adj} A = \left[ \begin{array}{rrr} 37 & -10 & 2 \\ -9 & 3 & 0 \\ 17 & -5 & 1 \end{array}\right] ^T = \left[ \begin{array}{rrr} 37 & -9 & 17 \\ -10 & 3 & -5 \\ 2 & 0 & 1 \end{array}\right] \nonumber \]

The computation of \(A (\text{adj} A)\) gives

\[A(\text{adj} A) = \left[ \begin{array}{rrr} 1 & 3 & -2 \\ 0 & 1 & 5 \\ -2 & -6 & 7 \end{array}\right] \left[ \begin{array}{rrr} 37 & -9 & 17 \\ -10 & 3 & -5 \\ 2 & 0 & 1 \end{array}\right] = \left[ \begin{array}{rrr} 3 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 3 \end{array}\right] = 3I \nonumber \]

and the reader can verify that also \((\text{adj} A)A = 3I\). Hence, analogy with the \(2 \times 2\) case would indicate that \(\det A = 3\); this is, in fact, the case.

The relationship \(A(\text{adj} A) = (\det A)I\) holds for any square matrix \(A\). To see why this is so, consider the general \(3 \times 3\) case. Writing \(c_{ij}(A) = c_{ij}\) for short, we have

\[\text{adj} A = \left[ \begin{array}{rrr} c_{11} & c_{12} & c_{13} \\ c_{21} & c_{22} & c_{23} \\ c_{31} & c_{32} & c_{33} \end{array}\right]^T = \left[ \begin{array}{rrr} c_{11} & c_{21} & c_{31} \\ c_{12} & c_{22} & c_{32} \\ c_{13} & c_{23} & c_{33} \end{array}\right] \nonumber \]

If \(A = \left[ a_{ij} \right]\) in the usual notation, we are to verify that \(A(\text{adj} A) = (\det A)I\). That is,

\[A(\text{adj} A) =\left[ \begin{array}{rrr} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array}\right] \left[ \begin{array}{rrr} c_{11} & c_{21} & c_{31} \\ c_{12} & c_{22} & c_{32} \\ c_{13} & c_{23} & c_{33} \end{array}\right] = \left[ \begin{array}{ccc} \det A & 0 & 0 \\ 0 & \det A & 0 \\ 0 & 0 & \det A \end{array}\right] \nonumber \]

Consider the \((1, 1)\)-entry in the product. It is given by \(a_{11}c_{11} + a_{12}c_{12} + a_{13}c_{13}\), and this is just the cofactor expansion of \(\det A\) along the first row of \(A\). Similarly, the \((2, 2)\)-entry and the \((3, 3)\)-entry are the cofactor expansions of \(\det A\) along rows \(2\) and \(3\), respectively.

So it remains to be seen why the off-diagonal elements in the matrix product \(A(\text{adj} A)\) are all zero. Consider the \((1, 2)\)-entry of the product. It is given by \(a_{11}c_{21} + a_{12}c_{22} + a_{13}c_{23}\). This looks like the cofactor expansion of the determinant of some matrix. To see which, observe that \(c_{21}\), \(c_{22}\), and \(c_{23}\) are all computed by deleting row \(2\) of \(A\) (and one of the columns), so they remain the same if row \(2\) of \(A\) is changed. In particular, if row \(2\) of \(A\) is replaced by row \(1\), we obtain

\[a_{11}c_{21}+a_{12}c_{22}+a_{13}c_{23} = \det \left[ \begin{array}{rrr} a_{11} & a_{12} & a_{13} \\ a_{11} & a_{12} & a_{13} \\ a_{31} & a_{32} & a_{33} \end{array}\right] = 0 \nonumber \]

where the expansion is along row \(2\) and where the determinant is zero because two rows are identical. A similar argument shows that the other off-diagonal entries are zero.

This argument works in general and yields the first part of Theorem [thm:008370]. The second assertion follows from the first by multiplying through by the scalar \(\frac{1}{\det A}\).

Adjugate Formula008370 If A is any square matrix, then

\[A(\text{adj} A) = (\det A)I = (\text{adj} A)A \nonumber \]

In particular, if det A \(\neq\) 0, the inverse of A is given by

\[A^{-1} =\frac{1}{\det A}\text{adj} A \nonumber \]

It is important to note that this theorem is not an efficient way to find the inverse of the matrix \(A\). For example, if \(A\) were \(10 \times 10\), the calculation of \(\text{adj} A\) would require computing \(10^{2} = 100\) determinants of \(9 \times 9\) matrices! On the other hand, the matrix inversion algorithm would find \(A^{-1}\) with about the same effort as finding \(\det A\). Clearly, Theorem [thm:008370] is not a practical result: its virtue is that it gives a formula for \(A^{-1}\) that is useful for theoretical purposes.

008382 Find the \((2, 3)\)-entry of \(A^{-1}\) if \(A = \left[ \begin{array}{rrr} 2 & 1 & 3 \\ 5 & -7 & 1 \\ 3 & 0 & -6 \end{array}\right]\).

First compute

\[\det A = \left| \begin{array}{rrr} 2 & 1 & 3 \\ 5 & -7 & 1 \\ 3 & 0 & -6 \end{array} \right| = \left| \begin{array}{rrr} 2 & 1 & 7 \\ 5 & -7 & 11 \\ 3 & 0 & 0 \end{array} \right| = 3 \left| \begin{array}{rr} 1 & 7 \\ -7 & 11 \end{array}\right| = 180 \nonumber \]

Since \(A^{-1} = \frac{1}{\det A}\text{adj} A = \frac{1}{180} \left[ c_{ij}(A)\right] ^T\), the \((2, 3)\)-entry of \(A^{-1}\) is the \((3, 2)\)-entry of the matrix \(\frac{1}{180}\left[ c_{ij}(A) \right]\); that is, it equals \(\frac{1}{180} c_{32} (A) = \frac{1}{180} \left( - \left| \begin{array}{rr} 2 & 3 \\ 5 & 1 \end{array}\right| \right) = \frac{13}{180}.\)

008396 If \(A\) is \(n \times n\), \(n \geq 2\), show that \(\det (\text{adj} A) = (\det A)^{n-1}\).

Write \(d = \det A\); we must show that \(\det (\text{adj} A) = d^{n-1}\). We have \(A(\text{adj} A) = dI\) by Theorem [thm:008370], so taking determinants gives \(d\det (\text{adj} A) = d^{n}\). Hence we are done if \(d \neq 0\). Assume \(d = 0\); we must show that \(\det (\text{adj} A) = 0\), that is, \(\text{adj} A\) is not invertible. If \(A \neq 0\), this follows from \(A(\text{adj} A) = dI = 0\); if \(A = 0\), it follows because then \(\text{adj} A = 0\).

Cramer’s Rule

Theorem [thm:008370] has a nice application to linear equations. Suppose

\[A\mathbf{x}=\mathbf{b} \nonumber \]

is a system of \(n\) equations in \(n\) variables \(x_{1}, x_{2}, \dots , x_{n}\). Here \(A\) is the \(n \times n\) coefficient matrix, and \(\mathbf{x}\) and \(\mathbf{b}\) are the columns

\[\mathbf{x} = \left[ \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right] \mbox{ and } \mathbf{b} = \left[ \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right] \nonumber \]

of variables and constants, respectively. If \(\det A \neq 0\), we left multiply by \(A^{-1}\) to obtain the solution \(\mathbf{x} = A^{-1}\mathbf{b}\). When we use the adjugate formula, this becomes

\[\begin{aligned} \left[ \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right] &= \frac{1}{\det A} (\text{adj} A)\mathbf{b} \\ &= \frac{1}{\det A} \left[ \begin{array}{cccc} c_{11}(A) & c_{21}(A) & \cdots & c_{n1}(A) \\ c_{12}(A) & c_{22}(A) & \cdots & c_{n2}(A) \\ \vdots & \vdots & & \vdots \\ c_{1n}(A) & c_{2n}(A) & \cdots & c_{nn}(A) \end{array}\right] \left[ \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right] \end{aligned} \nonumber \]

Hence, the variables \(x_{1}, x_{2}, \dots, x_{n}\) are given by

\[\begin{aligned} x_1 &= \frac{1}{\det A} \left[ b_1c_{11}(A) + b_2c_{21}(A) + \cdots + b_nc_{n1}(A)\right] \\ x_2 &= \frac{1}{\det A} \left[ b_1c_{12}(A) + b_2c_{22}(A) + \cdots + b_nc_{n2}(A)\right] \\ & \hspace{5em} \vdots \hspace{5em} \vdots\\ x_n &= \frac{1}{\det A} \left[ b_1c_{1n}(A) + b_2c_{2n}(A) + \cdots + b_nc_{nn}(A)\right] \end{aligned} \nonumber \]

Now the quantity \(b_{1}c_{11}(A) + b_{2}c_{21}(A) + \cdots + b_{n}c_{n1}(A)\) occurring in the formula for \(x_{1}\) looks like the cofactor expansion of the determinant of a matrix. The cofactors involved are \(c_{11}(A), c_{21}(A), \dots, c_{n1}(A)\), corresponding to the first column of \(A\). If \(A_{1}\) is obtained from \(A\) by replacing the first column of \(A\) by \(\mathbf{b}\), then \(c_{i1}(A_{1}) = c_{i1}(A)\) for each \(i\) because column \(1\) is deleted when computing them. Hence, expanding \(\det (A_{1})\) by the first column gives

\[\begin{aligned} \det A_1 &= b_1c_{11}(A_1) + b_2c_{21}(A_1) + \cdots + b_nc_{n1}(A_1) \\ &= b_1c_{11}(A) + b_2c_{21}(A) + \cdots + b_nc_{n1}(A)\\ &= (\det A)x_1 \end{aligned} \nonumber \]

Hence, \(x_1 = \frac{\det A_1}{\det A}\) and similar results hold for the other variables.

Cramer’s Rule008446 If \(A\) is an invertible \(n \times n\) matrix, the solution to the system

\[A\mathbf{x}=\mathbf{b} \nonumber \]

of \(n\) equations in the variables \(x_{1}, x_{2}, \dots, x_{n}\) is given by

\[x_1 = \frac{\det A_1}{\det A}, \; x_2 = \frac{\det A_2}{\det A}, \;\cdots, \; x_n = \frac{\det A_n}{\det A} \nonumber \]

where, for each \(k\), \(A_k\) is the matrix obtained from \(A\) by replacing column \(k\) by \(\mathbf{b}\).

008457 Find \(x_{1}\), given the following system of equations.

\[ \begin{array}{rrrrrrr} 5x_1 & + & x_2 & - & x_3 & = & 4\\ 9x_1& + & x_2 & - & x_3 & = & 1 \\ x_1& - & x_2 & + & 5x_3 & = & 2 \\ \end{array} \nonumber \]

Compute the determinants of the coefficient matrix \(A\) and the matrix \(A_{1}\) obtained from it by replacing the first column by the column of constants.

\[\begin{aligned} \det A &= \det \left[ \begin{array}{rrr} 5 & 1 & -1 \\ 9 & 1 & -1 \\ 1 & -1 & 5 \end{array}\right] = -16 \\ \det A_1 &= \det \left[ \begin{array}{rrr} 4 & 1 & -1 \\ 1 & 1 & -1 \\ 2 & -1 & 5 \end{array}\right] = 12\end{aligned} \nonumber \]

Hence, \(x_1 = \frac{\det A_1}{\det A} = -\frac{3}{4}\) by Cramer’s rule.

Cramer’s rule is not an efficient way to solve linear systems or invert matrices. True, it enabled us to calculate \(x_{1}\) here without computing \(x_{2}\) or \(x_{3}\). Although this might seem an advantage, the truth of the matter is that, for large systems of equations, the number of computations needed to find all the variables by the gaussian algorithm is comparable to the number required to find one of the determinants involved in Cramer’s rule. Furthermore, the algorithm works when the matrix of the system is not invertible and even when the coefficient matrix is not square. Like the adjugate formula, then, Cramer’s rule is not a practical numerical technique; its virtue is theoretical.

Polynomial Interpolation

008475

A forester wants to estimate the age (in years) of a tree by measuring the diameter of the trunk (in cm). She obtains the following data:

to 15cm |l|c|c|c| & Tree 1 & Tree 2 & Tree 3
Trunk Diameter & \(5\) & \(10\) & \(15\)
Age & \(3\) & \(5\) & \(6\)

Estimate the age of a tree with a trunk diameter of 12 cm.

The forester decides to “fit” a quadratic polynomial

\[p(x) = r_0 + r_1x + r_2x^2 \nonumber \]

to the data, that is choose the coefficients \(r_{0}\), \(r_{1}\), and \(r_{2}\) so that \(p(5) = 3\), \(p(10) = 5\), and \(p(15) = 6\), and then use \(p(12)\) as the estimate. These conditions give three linear equations:

\[ \begin{array}{rrrrrrr} r_0 & + & 5r_1 & + & 25r_2 & = & 3\\ r_0 & + & 10r_1 & + & 100r_2 & = & 5\\ r_0 & + & 15r_1 & + & 225r_2 & = & 6 \end{array} \nonumber \]

The (unique) solution is \(r_0=0, r_1 = \frac{7}{10},\) and \(r_2 = -\frac{1}{50}\), so

\[p(x) = \frac{7}{10}x - \frac{1}{50}x^2 = \frac{1}{50}x (35-x) \nonumber \]

Hence the estimate is \(p(12) = 5.52\).

As in Example [exa:008475], it often happens that two variables \(x\) and \(y\) are related but the actual functional form \(y = f(x)\) of the relationship is unknown. Suppose that for certain values \(x_{1}, x_{2}, \dots, x_{n}\) of \(x\) the corresponding values \(y_{1}, y_{2}, \dots, y_{n}\) are known (say from experimental measurements). One way to estimate the value of \(y\) corresponding to some other value \(a\) of \(x\) is to find a polynomial¹

\[p(x) = r_0 + r_1x + r_2x^2 + \cdots + r_{n-1}x^{n-1} \nonumber \]

that “fits” the data, that is \(p(x_{i}) = y_{i}\) holds for each \(i = 1, 2, \dots , n\). Then the estimate for \(y\) is \(p(a)\). As we will see, such a polynomial always exists if the \(x_{i}\) are distinct.

The conditions that \(p(x_{i}) = y_{i}\) are

\[ \def\arraystretch{1.25} \begin{array}{ccccccccccc} r_0 & + & r_1x_1 & + & r_2x_1^2 & + & \cdots & + & r_{n-1}x_1^{n-1} & = &y_1 \\ r_0 & + & r_1x_2 & + & r_2x_2^2 & + & \cdots & + & r_{n-1}x_2^{n-1} & = &y_2 \\ & \vdots & & \vdots & & \vdots & & & \vdots & \vdots & \\ r_0 & + & r_1x_n & + & r_2x_n^2 & + & \cdots & + & r_{n-1}x_n^{n-1} & = & y_n \end{array} \nonumber \]

In matrix form, this is

\[\label{eq:polymatrixform} \left[ \begin{array}{ccccc} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1}\\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \end{array}\right] \left[ \begin{array}{c} r_0 \\ r_1 \\ \vdots \\ r_{n-1} \end{array} \right] = \left[ \begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_n \end{array} \right] \]

It can be shown (see Theorem [thm:008552]) that the determinant of the coefficient matrix equals the product of all terms \((x_{i} - x_{j})\) with \(i > j\) and so is nonzero (because the \(x_{i}\) are distinct). Hence the equations have a unique solution \(r_{0}, r_{1}, \dots, r_{n-1}\). This proves

008520 Let \(n\) data pairs \((x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})\) be given, and assume that the \(x_{i}\) are distinct. Then there exists a unique polynomial

\[p(x) = r_0 + r_1x + r_2x^2 + \cdots + r_{n-1}x^{n-1} \nonumber \]

such that \(p(x_{i}) = y_{i}\) for each \(i = 1, 2, \dots, n\).

The polynomial in Theorem [thm:008520] is called the interpolating polynomial for the data.

We conclude by evaluating the determinant of the coefficient matrix in Equation [eq:polymatrixform]. If \(a_{1}, a_{2}, \dots, a_{n}\) are numbers, the determinant

\[\det \left[ \begin{array}{ccccc} 1 & a_1 & a_1^2 & \cdots & a_1^{n-1}\\ 1 & a_2 & a_2^2 & \cdots & a_2^{n-1}\\ 1 & a_3 & a_3^2 & \cdots & a_3^{n-1}\\ \vdots & \vdots & \vdots & & \vdots \\ 1 & a_n & a_n^2 & \cdots & a_n^{n-1}\\ \end{array}\right] \nonumber \]

is called a Vandermonde determinant.² There is a simple formula for this determinant. If \(n = 2\), it equals \((a_{2} - a_{1})\); if \(n = 3\), it is \((a_{3} - a_{2})(a_{3} - a_{1})(a_{2} - a_{1})\) by Example [exa:007851]. The general result is the product

\[\prod_{ 1 \le j < i \le n} (a_i - a_j) \nonumber \]

of all factors \((a_{i} - a_{j})\) where \(1 \leq j < i \leq n\). For example, if \(n = 4\), it is

\[(a_4-a_3)(a_4-a_2)(a_4-a_1)(a_3-a_2)(a_3-a_1)(a_2-a_1) \nonumber \]

008552 Let \(a_{1}, a_{2}, \dots , a_{n}\) be numbers where \(n \geq 2\). Then the corresponding Vandermonde determinant is given by

\[\det \left[ \begin{array}{ccccc} 1 & a_1 & a_1^2 & \cdots & a_1^{n-1}\\ 1 & a_2 & a_2^2 & \cdots & a_2^{n-1}\\ 1 & a_3 & a_3^2 & \cdots & a_3^{n-1}\\ \vdots & \vdots & \vdots & & \vdots \\ 1 & a_n & a_n^2 & \cdots & a_n^{n-1}\\ \end{array}\right] = \prod_{1 \le j < i \le n}(a_i - a_j) \nonumber \]

We may assume that the \(a_{i}\) are distinct; otherwise both sides are zero. We proceed by induction on \(n \geq 2\); we have it for \(n = 2, 3\). So assume it holds for \(n - 1\). The trick is to replace \(a_{n}\) by a variable \(x\), and consider the determinant

\[p(x) = \det \left[ \begin{array}{ccccc} 1 & a_1 & a_1^2 & \cdots & a_1^{n-1} \\ 1 & a_2 & a_2^2 & \cdots & a_2^{n-1} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & a_{n-1} & a_{n-1}^2 & \cdots & a_{n-1}^{n-1} \\ 1 & x & x^2 & \cdots & x^{n-1} \end{array} \right] \nonumber \]

Then \(p(x)\) is a polynomial of degree at most \(n - 1\) (expand along the last row), and \(p(a_{i}) = 0\) for each \(i = 1, 2, \dots, n - 1\) because in each case there are two identical rows in the determinant. In particular, \(p(a_{1}) = 0\), so we have \(p(x) = (x - a_{1})p_{1}(x)\) by the factor theorem (see Appendix [chap:appdpolynomials]). Since \(a_{2} \neq a_{1}\), we obtain \(p_{1}(a_{2}) = 0\), and so \(p_{1}(x) = (x - a_{2})p_{2}(x)\). Thus \(p(x) = (x - a_{1})(x - a_{2})p_{2}(x)\). As the \(a_{i}\) are distinct, this process continues to obtain

\[\label{eq:polynomial} p(x) = (x-a_1)(x-a_2) \cdots (x-a_{n-1})d \]

where \(d\) is the coefficient of \(x^{n-1}\) in \(p(x)\). By the cofactor expansion of \(p(x)\) along the last row we get

\[d = (-1)^{n+n}\det \left[ \begin{array}{ccccc} 1 & a_1 & a_1^2 & \cdots & a_1^{n-2} \\ 1 & a_2 & a_2^2 & \cdots & a_2^{n-2} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & a_{n-1} & a_{n-1}^2 & \cdots & a_{n-1}^{n-2} \end{array}\right] \nonumber \]

Because \((-1)^{n+n}=1\) the induction hypothesis shows that \(d\) is the product of all factors \((a_{i} - a_{j})\) where \(1 \leq j < i \leq n - 1\). The result now follows from Equation [eq:polynomial] by substituting \(a_{n}\) for \(x\) in \(p(x)\).

If \(A\) and \(B\) are \(n \times n\) matrices we must show that

\[\label{eq:polyproof1} \det (AB) = \det A \det B \]

Recall that if \(E\) is an elementary matrix obtained by doing one row operation to \(I_{n}\), then doing that operation to a matrix \(C\) (Lemma [lem:005213]) results in \(EC\). By looking at the three types of elementary matrices separately, Theorem [thm:007779] shows that

\[\label{eq:polyproof2} \det (EC) = \det E \det C \quad \mbox{ for any matrix } C \]

Thus if \(E_{1}, E_{2}, \dots, E_{k}\) are all elementary matrices, it follows by induction that

\[\label{eq:polyproof3} \det (E_k \cdots E_2E_1C) = \det E_k \cdots \det E_2 \det E_1 \det C \mbox{ for any matrix } C \]

Lemma. If \(A\) has no inverse, then \(\det A = 0\).

Proof. Let \(A \to R\) where \(R\) is reduced row-echelon, say \(E_{n} \cdots E_{2}E_{1}A = R\). Then \(R\) has a row of zeros by Part (4) of Theorem [thm:004553], and hence \(\det R = 0\). But then Equation [eq:polyproof3] gives \(\det A = 0\) because \(\det E \neq 0\) for any elementary matrix \(E\). This proves the Lemma.

Now we can prove Equation [eq:polyproof1] by considering two cases.

Case 1. \(A\) has no inverse. Then \(AB\) also has no inverse (otherwise \(A[B(AB)^{-1}] = I\) so \(A\) is invertible by Corollary [cor:004612] to Theorem [thm:004553]). Hence the above Lemma (twice) gives

\[\det (AB) = 0 = 0 \det B = \det A \det B \nonumber \]

proving Equation [eq:polyproof1] in this case.

Case 2. \(A\) has an inverse. Then \(A\) is a product of elementary matrices by Theorem [thm:005336], say \(A = E_{1}E_{2}\cdots E_{k}\). Then Equation [eq:polyproof3] with \(C = I\) gives

\[\det A = \det (E_1E_2\cdots E_k)= \det E_1 \det E_2 \cdots \det E_k \nonumber \]

But then Equation [eq:polyproof3] with \(C = B\) gives

\[\det (AB) = \det \left[(E_1E_2\cdots E_k)B \right]= \det E_1 \det E_2 \cdots \det E_k \det B = \det A \det B \nonumber \]

and Equation [eq:polyproof1] holds in this case too.

---

1. A polynomial is an expression of the form \(a_{0} + a_{1}x + a_{2}x^{2} + \dots + a_{n}x^{n}\) where the \(a_{i}\) are numbers and \(x\) is a variable. If \(a_{n} \neq 0\), the integer \(n\) is called the degree of the polynomial, and \(a_{n}\) is called the leading coefficient. See Appendix [chap:appdpolynomials].↩
2. Alexandre Théophile Vandermonde (1735–1796) was a French mathematician who made contributions to the theory of equations.↩