Feb 19

Cramer's rule and invertibility criterion

Cramer's rule and invertibility criterion

Consequences of multilinearity

For a fixed j, \det A is a linear function of column A^{(j)}. Such a linear function generates a row-vector L_{j} by way of a formula (see Exercise 3)

(1) \det A=L_jA^{(j)}.

Exercise 1. In addition to (1), we have

(2) L_jA^{(k)}=0 for any k\neq l.

Proof. Here and in the future it is useful to introduce the coordinate representation for L_j=(l_{j1},...,l_{jn}) and put

(3) L=\left(\begin{array}{c}L_1 \\... \\L_n\end{array}\right).

Then we can write (1) as \det A=\sum_{i=1}^nl_{ji}a_{ij}. Here the element l_{ji} does not involve a_{ij} and therefore by the different-columns-different-rows rule it does not involve elements of the entire column A^{(j)}. Hence, the vector L_j does not involve elements of the column A^{(j)}.

Let A^{\prime } denote the matrix obtained from A by replacing column A^{(j)} with column A^{(k)}. The vector L_j for the matrix A^{\prime } is the same as for A because both vectors depend on the elements from columns other than the column numbered j. Since A^\prime contains linearly dependent (actually two identical) columns, \det A^\prime=0. Using in (1) A^\prime instead of A we get 0=\det A^\prime=L_jA^{(k)}, as required.

After reading the next two sections, come back and read this statement again to appreciate its power and originality.

Cramer's rule

Exercise 2. Suppose \det A\neq 0. For any y\in R^n denote B_j the matrix formed by replacing the j-th column of A by the column vector y. Then the solution of the system Ax=y exists and the components of x are given by

x_j=\frac{\det B_j}{\det A},\ j=1,...,n.

Proof. Premultiply Ax=y by L_{j}:

(4) L_jy=L_jAx=\left(L_jA^{(1)},...,L_jA^{(n)}\right)x=(0,...,\det A,...,0)x.

Here we applied (1) and (2) (the j-th component of the vector (0,...,\det  A,...,0) is \det A and all others are zeros). From (4) it follows that (\det  A)x_{j}=L_{j}y. On the other hand, from (1) we have \det B_j=L_jy (the vector L_j for B_j is the same as for A, see the proof of Exercise 1). The last two equations prove the statement.

Invertibility criterion

Exercise 3. A is invertible if and only if \det A\neq 0.

Proof. If A is invertible, then AA^{-1}=I. By multiplicativity of determinant and Axiom 3 this implies \det A\det (A^{-1})=1. Thus, \det  A\neq 0.

Conversely, suppose \det A\neq 0. (1), (2) and (3) imply

(5) LA=\left(\begin{array}{c}L_1 \\... \\L_n\end{array}\right) (A^{(1)},...,A^{(n)})=\left(\begin{array}{ccc}L_1A^{(1)}&...&L_1A^{(n)} \\...&...&... \\L_nA^{(1)}&...&L_nA^{(n)}\end{array}  \right)

=\left(\begin{array}{ccc}\det A&...&0 \\...&...&... \\0&...&\det A\end{array}  \right)=\det A\times I.

This means that the matrix \frac{1}{\det A}L is the inverse of A. Recall that existence of the left inverse implies that of the right inverse, so A is invertible.

Definition 1. The matrix L is more than a transient technical twist; it is called an adjugate matrix and property (5), correspondingly, is called an adjugate identity.