Transpose, column operations, and Cramer's rule

Proof of the finite real matrix product laws

Let $m,n,p,q$ be positive integers, let $A\in\mathbb R^{m\times n}$, $B\in\mathbb R^{n\times p}$, and $C\in\mathbb R^{p\times q}$. All the following arguments use the row-by-column definition and finite real sums. For any output position $(i,\ell)$,

$$\begin{aligned} ((AB)C)_{i\ell} &=\sum_{k=1}^{p}\left(\sum_{j=1}^{n}a_{ij}b_{jk}\right)c_{k\ell}\\ &=\sum_{j=1}^{n}a_{ij}\left(\sum_{k=1}^{p}b_{jk}c_{k\ell}\right) =(A(BC))_{i\ell}. \end{aligned}$$

The middle equality only reorders two finite sums and uses real distributivity. Both products are $m\times q$, so equality at every position proves associativity. No factor has changed its order.

For $D\in\mathbb R^{n\times p}$, the same definition gives

$$[A(B+D)]_{ik}=\sum_{j=1}^{n}a_{ij}(b_{jk}+d_{jk}) =(AB)_{ik}+(AD)_{ik}.$$

For $E\in\mathbb R^{m\times n}$, it gives

$$[(A+E)B]_{ik}=\sum_{j=1}^{n}(a_{ij}+e_{ij})b_{jk} =(AB)_{ik}+(EB)_{ik}.$$

Thus both distributive laws hold with the displayed matching sizes. For every real scalar $c$,

$$[(cA)B]_{ik}=\sum_j(ca_{ij})b_{jk} =c\sum_j a_{ij}b_{jk} =\sum_j a_{ij}(cb_{jk})=[A(cB)]_{ik},$$

proving $(cA)B=c(AB)=A(cB)$ by entrywise equality. In particular, for $x,y\in\mathbb R^n$ and real $s,t$,

$$[A(sx+ty)]_i=\sum_j a_{ij}(sx_j+ty_j) =s(Ax)_i+t(Ay)_i.$$

This proves the matrix-vector linearity used when comparing solutions of the same linear system. All identities concern compatible finite real matrices; they do not assert commutativity or cancellation of arbitrary matrix factors.

Build the elementary matrix from the identity

Suppose an elementary row operation $\rho$ is meant to act on matrices with $p$ rows. Start with the identity matrix $I_p$, apply the same elementary row operation to $I_p$, and call the result $E_\rho$. All scalars are taken from the underlying field of the matrices; in particular, every nonzero scaling factor $c$ has a reciprocal $1/c$ in that field.

Definition

Elementary row-operation matrix

The elementary row-operation matrix associated with an elementary row operation $\rho$ on $p$-row matrices is the $p \times p$ matrix obtained by applying $\rho$ to $I_p$.

This matrix is also called an elementary matrix. The longer name keeps its connection with the specified row operation visible.

Equivalently,

$$E_\rho = \rho(I_p).$$

The reason this definition is useful is the following theorem.

Theorem

Elementary row operations are left multiplication

Let $A$ be any matrix with $p$ rows. If $\rho$ is one elementary row operation and $\rho(A)$ denotes the result of applying it to $A$, then

$$\rho(A) = E_\rho A.$$

So applying that elementary row operation to $A$ is the same as multiplying $A$ on the left by the elementary row-operation matrix obtained from the same operation on $I_p$.

The multiplication must be on the left. Row operations change rows by mixing rows. Left multiplication forms new rows of $A$ as linear combinations of old rows of $A$. Right multiplication would instead mix columns.

The dimensions make the same point. If $A$ is $p \times n$, then $E_\rho$ is $p \times p$, so $E_\rho A$ is defined and remains $p \times n$. There is no assumption that $A$ is square. By contrast, a column-operation matrix acting on these same $n$ columns would have size $n \times n$ and multiply on the right.

Why left multiplication performs the operation

Proof

Verify the three elementary cases row by row

Write the rows of an arbitrary $p \times n$ matrix $A$ as $a_1,a_2,\ldots,a_p$, and let $e_k^{\mathsf T}$ denote row $k$ of $I_p$. The basic identity

$$e_k^{\mathsf T}A=a_k$$

says that a row of a left multiplier selects the corresponding row of $A$. Now check the three elementary operations.

1. For $R_i\leftrightarrow R_j$, the matrix $E_\rho$ has row $i$ equal to $e_j^{\mathsf T}$, row $j$ equal to $e_i^{\mathsf T}$, and every other row $k$ equal to $e_k^{\mathsf T}$. Thus the rows of $E_\rho A$ are the rows of $A$ with precisely rows $i$ and $j$ exchanged.

2. For $R_i\leftarrow cR_i$, where $c\ne0$, row $i$ of $E_\rho$ is $c e_i^{\mathsf T}$ and all other rows are unchanged. Hence row $i$ of the product is

   $$(c e_i^{\mathsf T})A=c a_i,$$

   while row $k$ remains $a_k$ for $k\ne i$.

3. For $R_j\leftarrow R_j+cR_i$, where $i\ne j$, row $j$ of $E_\rho$ is $e_j^{\mathsf T}+c e_i^{\mathsf T}$ and every other row is unchanged. Therefore the new row $j$ is

   $$(e_j^{\mathsf T}+c e_i^{\mathsf T})A=a_j+c a_i,$$

   exactly as prescribed.

These cases exhaust the elementary row operations, so they prove $E_\rho A=\rho(A)$ for every compatible $A$. The proof does not claim that an arbitrary manipulation of rows has such an elementary matrix; $\rho$ must be one of the three operations just checked.

Acting on an augmented matrix

Suppose $Ax=b$ is represented by the augmented matrix $[A\mid b]$. An elementary row operation must act on the full augmented matrix, not separately on whichever entries happen to be convenient. The multiplication identity is

$$E_\rho[A\mid b]=[E_\rho A\mid E_\rho b].$$

Thus the coefficients and the right-hand side undergo the same combination of rows. A vector $x$ satisfies $Ax=b$ if and only if it satisfies $E_\rho Ax=E_\rho b$: the forward implication follows by multiplying the equation by $E_\rho$, and the reverse implication follows by applying the reverse elementary operation. This is the precise reason the solution set is preserved.

Changing only $A$ while leaving $b$ fixed, or changing only $b$, generally produces a different system. The augmentation bar is therefore a visual separator, not a boundary at which a row operation may stop.

A sequence of elementary row operations becomes one matrix product

The real payoff is not just representing one elementary row operation. A whole sequence of elementary row operations becomes one product of elementary row-operation matrices.

Theorem

A sequence of elementary row operations as a product

Suppose

$$A_1 \xrightarrow{\rho_1} A_2 \xrightarrow{\rho_2} A_3 \xrightarrow{\rho_3} \cdots \xrightarrow{\rho_k} A_{k+1}.$$

Then

$$A_{k+1} = E_{\rho_k}E_{\rho_{k-1}}\cdots E_{\rho_2}E_{\rho_1}A_1.$$

Here every $\rho_j$ is an elementary row operation on matrices with the same number of rows. The product represents the whole sequence, although the product itself need not be a single elementary row-operation matrix.

The order in this formula is important. The first row operation appears closest to $A_1$, because it is applied first:

$$A_2 = E_{\rho_1}A_1, \qquad A_3 = E_{\rho_2}A_2 = E_{\rho_2}E_{\rho_1}A_1.$$

Worked example

Two row operations combined

Let

$$A = \begin{bmatrix} 1 & 0 & 1\\ 0 & 2 & 1\\ 1 & 0 & 0 \end{bmatrix}.$$

Apply

$$\rho_1:\ R_2 \leftarrow R_2 + R_1, \qquad \rho_2:\ R_1 \leftarrow R_1 + 2R_2.$$

The corresponding row-operation matrices are

$$E_{\rho_1} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}, \qquad E_{\rho_2} = \begin{bmatrix} 1 & 2 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}.$$

After both operations, the result is

$$E_{\rho_2}E_{\rho_1}A = \begin{bmatrix} 3&2&0\\ 1&1&0\\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&0&1\\ 0&2&1\\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 3&4&5\\ 1&2&2\\ 1&0&0 \end{bmatrix}.$$

Instead of multiplying $E_{\rho_2}E_{\rho_1}$ directly, you can also obtain this combined matrix by applying the same two elementary row operations to $I_3$ in the same order. The final numerical matrix also confirms that the second operation uses the already-updated row $2$.

Reverse row operations and inverses

Every elementary row operation has a reverse operation:

• the reverse of $R_j \leftarrow R_j + cR_i$ is $R_j \leftarrow R_j - cR_i$;
• the reverse of $R_i \leftarrow cR_i$, with $c \ne 0$, is $R_i \leftarrow (1/c)R_i$;
• the reverse of a row swap is the same row swap.

This gives a precise matrix statement.

Theorem

Elementary row-operation matrices are invertible

Every elementary row-operation matrix is invertible. Its inverse is the elementary row-operation matrix corresponding to the reverse elementary row operation.

Proof

Why the reverse matrix is a two-sided inverse

Let $E_\rho$ represent an elementary row operation $\rho$, and let $E_{\rho^{-1}}$ represent the reverse elementary operation. For every matrix $X$ with $p$ rows, applying $\rho$ and then reversing it restores $X$. By the left-multiplication theorem,

$$E_{\rho^{-1}}E_\rho X=X.$$

This statement holds for every such $X$; in particular, put $X=I_p$ to obtain $E_{\rho^{-1}}E_\rho=I_p$. Reversing first and then applying $\rho$ similarly gives $E_\rho E_{\rho^{-1}}=I_p$. Hence

$$E_\rho^{-1}=E_{\rho^{-1}}.$$

Concretely, a swap is its own inverse, scaling by $c\ne0$ is undone by scaling by $1/c$, and adding $c$ times row $i$ to row $j$ is undone by adding $-c$ times row $i$ to row $j$.

For example, if

$$E = \begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

performs $R_2 \leftarrow R_2 + 3R_1$, then

$$E^{-1} = \begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

performs $R_2 \leftarrow R_2 - 3R_1$.

This is the algebraic reason elementary row operations are reversible, and it explains why row reduction is so closely connected to invertible matrices.

Proof

Undo the last operation first

Let $E_1,\ldots,E_k$ encode a chronological chain on matrices with $p$ rows, so its combined multiplier is $J=E_k\cdots E_1$. Each inverse $E_j^{-1}$ represents the reverse of the corresponding elementary operation. To recover the input, the first move must undo $E_k$, because that was the last change made to the rows. The remaining reverse moves undo $E_{k-1},\ldots,E_1$ in that order. Consequently the reverse multiplier is

$$K=E_1^{-1}E_2^{-1}\cdots E_k^{-1}.$$

There are two orders to distinguish: the time order of the reverse operations starts with $E_k^{-1}$, while the written product places that first action nearest the matrix being restored. For three steps, associativity gives

$$KJ=E_1^{-1}E_2^{-1}(E_3^{-1}E_3)E_2E_1 =E_1^{-1}(E_2^{-1}E_2)E_1=I_p.$$

The other product $JK$ cancels adjacent inverse pairs starting with $E_1E_1^{-1}$ and also equals $I_p$. The same successive cancellation works for any finite chain. No factors have been commuted, and the argument does not require the matrix being transformed to be square.

Apply this reading to the earlier two-operation example. Its combined multiplier is $E_{\rho_2}E_{\rho_1}$, so its inverse is $E_{\rho_1}^{-1}E_{\rho_2}^{-1}$. Starting from the final matrix, first subtract twice the current second row from the first, recovering $[1\ 0\ 1]$ as the first row. Then subtract that recovered first row from the second, recovering $[0\ 2\ 1]$. Reversing the chain means restoring the intermediate states, which explains the order without a memorized rule.

Finite elimination terminates and preserves the solution set

Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, with positive finite integers $m,n$. The permitted row operations are an exchange of two distinct rows, multiplication of a row by a nonzero scalar, and addition of a scalar multiple of one row to a different row. Their inverses are respectively the same exchange, multiplication by the reciprocal, and subtraction of that multiple. Applying an operation to the entire augmented array therefore preserves exactly the solutions of $Ax=b$: the new equations are consequences of the old, and its inverse gives the reverse implication. Each operation is also multiplication on the left by the result of applying it to the identity matrix, an invertible elementary matrix.

Scan the coefficient columns from left to right, maintaining the next unused row. If the current column has a nonzero entry in an unused row, exchange that row into the next position, divide by its nonzero pivot, and subtract multiples of it from every other row to clear that column. Advance the unused-row index. If every unused entry in the column is zero, skip the column. Previously chosen pivot columns remain unit columns: the current unused rows have zeros in them, so the new pivot row and every subsequent subtraction preserve those zeros and earlier pivots. There are only $n$ column scans and at most $\min(m,n)$ pivots, each with finitely many row operations. Thus the algorithm terminates. At its end, the nonzero coefficient rows have increasing pivot columns and zeros below and above each pivot; any remaining coefficient row is zero. This proves the reduced echelon form used below, without assuming it will eventually appear.

Classification and the homogeneous freedom

Write $r$ for the number of pivots in the coefficient part. A zero coefficient row with a nonzero transformed right side is the impossible equation $0=c$, so the system has no solution. Otherwise assign arbitrary real values to all $n-r$ nonpivot variables. In each pivot row, its pivot variable equals the transformed right side minus the displayed linear combination of these free variables; no other pivot variable occurs. These formulas both construct a solution and recover every solution. If $r=n$ the solution is unique. If $r<n$, changing a free variable changes the vector, giving infinitely many solutions.

For $Az=0$ the free variables can all be zero, giving the zero solution. If $r<n$, set one free variable to one and the others to zero, and use the pivot formulas. This constructs a nonzero homogeneous solution. If $r=n$, the formulas force every homogeneous variable to zero. For a consistent system, fixing one solution $x_p$, subtraction proves that every solution has the form $x_p+z$ with $Az=0$, and substitution proves the converse.

For square $A$, if every column has a pivot, the coefficient form is $I$. The product $E$ of the finitely many elementary matrices satisfies $EA=I$. Since $E$ is invertible, $A=E^{-1}$ and therefore also $AE=I$: $E$ is a two-sided inverse. If a pivot is missing, the nonzero homogeneous solution constructed above rules out any inverse. This also justifies applying the same row operations to $[A\mid I]$ to obtain $[I\mid A^{-1}]$ in the invertible case.

Build the determinant from smaller matrices

Definition

Submatrix, minor, and cofactor

Let $A=[a_{ij}]$ be an $n\times n$ matrix with $n\ge 2$. For indices $1\le i,j\le n$, delete row $i$ and column $j$ simultaneously. The resulting $(n-1)\times(n-1)$ matrix is the submatrix $A(i\mid j)$.

The minor belonging to $a_{ij}$ is the scalar

$$M_{ij}=\det\bigl(A(i\mid j)\bigr).$$

The cofactor belonging to $a_{ij}$ is the signed scalar

$$C_{ij}=(-1)^{i+j}M_{ij}.$$

The signs form a checkerboard whose upper-left sign is positive:

$$\begin{bmatrix} +&-&+&\cdots\\ -&+&-&\cdots\\ +&-&+&\cdots\\ \vdots&\vdots&\vdots&\ddots \end{bmatrix}.$$

The notation $A(i\mid j)$ names a matrix, $M_{ij}$ is a determinant of that matrix, and $C_{ij}$ is that scalar after the sign has been attached. Keeping these three objects distinct prevents a common double-sign error.

Definition

Recursive definition of the determinant

For a $1\times1$ matrix $[a_{11}]$, define

$$\det([a_{11}])=a_{11}.$$

For an $n\times n$ matrix with $n>1$, define its determinant by expansion along the first row:

$$\det(A)=\sum_{j=1}^{n}a_{1j}C_{1j} =\sum_{j=1}^{n}(-1)^{1+j}a_{1j}M_{1j}.$$

This is a definition, not yet a theorem about other rows or columns. Each minor in the sum has size $n-1$, so repeated use of the definition eventually reaches the $1\times1$ base case. No $0\times0$ determinant convention is needed: the submatrix and minor definitions are used only for $n\ge2$.

Arbitrary cofactor expansion from the recursive determinant

Let $A$ be real $n\times n$, $n\ge1$, with determinant defined by the one-by-one base case and first-row recursion. Let $S_n$ be the permutations of $1,\ldots,n$. Define the inversion number $\operatorname{inv}(\sigma)$ as the number of pairs $r<s$ with $\sigma(r)>\sigma(s)$, and put $\operatorname{sgn}(\sigma)=(-1)^{\operatorname{inv}(\sigma)}$.

Suppose $\sigma(i)=j$ and delete position $i$ and value $j$, keeping the relative orders of the remaining positions and values; the resulting permutation is $\tau\in S_{n-1}$. If $u$ entries before position $i$ are smaller than $j$, the inversions removed are $(i-1-u)+(j-1-u)=i+j-2-2u$. Consequently

$$\operatorname{sgn}(\sigma)=(-1)^{i+j}\operatorname{sgn}(\tau).$$

Define $P_n(A)=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{r=1}^n a_{r,\sigma(r)}$. For $n=1$, it is the recursive determinant. For $n>1$, grouping by $\sigma(1)=j$ and using the sign identity gives $P_n(A)=\sum_j(-1)^{1+j}a_{1j}P_{n-1}(A(1\mid j))$. Induction therefore proves $P_n(A)=\det A$.

Now fix any row $i$ and group the same finite permutation sum by $\sigma(i)=j$. Deletion is a bijection to all permutations of the corresponding minor, so

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

For a fixed column $j$, each permutation has a unique position $i$ with $\sigma(i)=j$. Grouping by that position gives

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

Both expansion formulas concern $n\ge2$, so no empty determinant convention was introduced. This proves the general expansion theorem without assuming alternating row rules or the determinant product theorem.

Why the structural rules follow

Zero rows and zero columns

Theorem

A zero row or zero column gives determinant zero

If every entry in one row or one column of a square matrix is zero, then its determinant is zero.

Theorem

A row or column with one possible nonzero entry

For a square matrix of size $n\ge2$, suppose all entries in row $k$ are zero except possibly $c_{k\ell}$. Then

$$\det(C)=c_{k\ell}(-1)^{k+\ell}\det\bigl(C(k\mid\ell)\bigr).$$

The same formula holds when all entries in column $\ell$ are zero except possibly $c_{k\ell}$. The formula includes the case $c_{k\ell}=0$.

For $n=1$, a matrix with a zero row is $[0]$, whose determinant is $0$ by the base definition. For $n\ge2$, expand along that row using the arbitrary-row theorem. Every term has a zero entry as its factor, so every term is zero and hence $\det(A)=0$.

The zero-column statement can be proved directly by induction, which makes the inheritance of the zero column explicit. For $n=1$, the only $1\times1$ matrix with a zero column is $[0]$, and its determinant is $0$. Assume the statement for $n=k$. Let $C$ be a $(k+1)\times(k+1)$ matrix with zero column $\ell$. Expand along the first row. The term from column $\ell$ is zero. In every other term, delete row $1$ and a column $j\ne\ell$; the original zero column survives as a zero column of the resulting $k\times k$ submatrix (with its index shifted when $j\lt\ell$). By the induction hypothesis each such submatrix has determinant zero. Hence every term is zero, proving $\det(C)=0$.

For the one-support theorem, the row case follows by expanding along row $k$: all terms except the $\ell$-term vanish. For the column case, expand along row $k$. The $\ell$-term remains. For each $j\ne\ell$, the submatrix $C(k\mid j)$ inherits a zero column from column $\ell$ of $C$, so its determinant is zero by the zero-column result. Therefore only $c_{k\ell}(-1)^{k+\ell}\det(C(k\mid\ell))$ remains. This is the precise reason that a sparse row or column collapses the calculation to one minor.

Triangular matrices

Theorem

Triangular determinant theorem

If $T$ is upper triangular or lower triangular, then

$$\det(T)=t_{11}t_{22}\cdots t_{nn}.$$

We prove the upper-triangular statement by induction on $n$. For $n=1$, it is the determinant definition. Suppose it holds for upper-triangular $k\times k$ matrices, and let $T$ be upper triangular of size $k+1$. Its last row has zero entries except possibly $t_{k+1,k+1}$. Expanding along that last row gives

$$\det(T)=t_{k+1,k+1}\det\bigl(T(k+1\mid k+1)\bigr),$$

because the sign is $(-1)^{2k+2}=1$. The retained submatrix is still upper triangular, with diagonal $t_{11},\ldots,t_{kk}$. By induction its determinant is $t_{11}\cdots t_{kk}$, giving the required product through $t_{k+1,k+1}$. For a lower-triangular matrix, expand along the first row, whose only possible nonzero entry is $t_{11}$; the retained submatrix is lower triangular with diagonal $t_{22},\ldots,t_{nn}$, and the same induction proves the result.

Multilinearity in one fixed row

Theorem

Multilinearity in one fixed row

Fix every row except row $p$. If the new row is $\alpha u+\beta v$, then

$$\det(\text{same rows except }\alpha u+\beta v) =\alpha\det(\text{same rows except }u) +\beta\det(\text{same rows except }v).$$

For $n=1$, the base definition gives

$$\det([\alpha a+\beta b])=\alpha a+\beta b =\alpha\det([a])+\beta\det([b]).$$

For $n\ge2$, fix every row except row $p$. Let matrices $A,B,C$ agree in all those fixed rows, and suppose their $p$th rows satisfy $c_p=\alpha a_p+\beta b_p$. For each column $j$, deleting row $p$ gives the same submatrix:

$$A(p\mid j)=B(p\mid j)=C(p\mid j).$$

Expanding $\det(C)$ along row $p$ and using the entrywise relation $c_{pj}=\alpha a_{pj}+\beta b_{pj}$ gives

$$\begin{aligned} \det(C) &=\sum_{j=1}^{n}(\alpha a_{pj}+\beta b_{pj})(-1)^{p+j}\det(C(p\mid j))\\ &=\alpha\det(A)+\beta\det(B). \end{aligned}$$

The equality works precisely because every other row is held fixed; changing two rows at once is a different statement.

Adjacent swaps and repeated rows

Theorem

Repeated rows force determinant zero

If a square matrix has two identical rows, then its determinant is $0$.

Let $A$ have adjacent rows $r_q,r_{q+1}$, and let $B$ be obtained by swapping those two physical rows. Expand $\det(A)$ along row $q$. Expand $\det(B)$ along row $q+1$, where the row $r_q$ has moved. For each column $j$, the retained submatrix in the two expansions is the same matrix: deleting the position occupied by $r_q$ leaves the other row in the same order. However, the signs differ:

$$(-1)^{q+1+j}=-(-1)^{q+j}.$$

The entries and minors therefore match term by term with the opposite sign, so $\det(B)=-\det(A)$. Swapping rows in positions $p\lt q$ can be realised by $2(q-p)-1$ adjacent swaps, an odd number, and hence also changes the sign.

If rows $p$ and $q$ of $A$ are identical, the matrix obtained by swapping them is still $A$. The swap result then gives $\det(A)=-\det(A)$. Since the entries are real, this implies $2\det(A)=0$ and therefore $\det(A)=0$. This proof does not rely on a later row-replacement rule.

Indexing and strategy

For each term, keep three objects visible: the selected entry, its submatrix after deleting one row and one column, and the minor obtained by taking that submatrix determinant. Write the checkerboard sign from the original row and column positions before evaluating the minor. When a minor is expanded again, its local indices guide the inner sign; they do not replace the outer sign.

The arbitrary-row and arbitrary-column theorem makes the choice of expansion line strategic. Choose a line with many zeros or simple surviving minors, and state that choice before calculating. A zero entry removes a branch immediately, whereas a zero minor must be established by its own calculation. The recursive first-row formula defines the determinant; arbitrary-line expansion is the theorem that permits this computational choice.

Transpose transfers determinant identities from rows to columns. Column linearity then makes it possible to isolate one coefficient in a linear combination: replacing a column creates repeated columns in every unwanted term. This cancellation gives Cramer’s rule and connects it to the adjoint identity.

Throughout this note, matrices and scalars are real; whenever a determinant is written, the matrix is square.

Transpose does not change determinant

Theorem

Determinant of a transpose

For every square matrix $A$,

$$\det(A^T)=\det(A).$$

Although the recursive definition uses the first row, transposition leaves its value unchanged.

Proof

A factorization proof of transpose invariance

If $A$ is singular, then $A^T$ is singular as well: transposing either inverse equation would turn an inverse for $A^T$ into an inverse for $A$. Thus both determinants are zero. If $A$ is invertible, write

$$A=E_1E_2\cdots E_k$$

as a product of elementary matrices. A swap or nonzero scaling elementary matrix is unchanged by transposition. The transpose of an addition matrix $I+cE_{ij}$ is $I+cE_{ji}$, which is another addition matrix with determinant one. Therefore $\det(E_r^T)=\det(E_r)$ for every factor, while

$$A^T=E_k^T\cdots E_2^TE_1^T.$$

The determinant product rule gives $\det(A^T)=\det(A)$. The matrix factors reverse order, but their determinant values are scalars, whose product may be reordered. This proof uses the factorization and row-operation results of 7.2. It supplies a derivation of the column expansion stated in 7.1 without using that column formula in the argument.

Theorem

Cofactor expansion along any column

For any fixed column $j$ of a square matrix $A=[a_{ij}]$, with $n\ge2$, where $M_{ij}$ is the minor determinant and $C_{ij}=(-1)^{i+j}M_{ij}$ is the cofactor,

$$\det(A)=a_{1j}C_{1j}+a_{2j}C_{2j}+\cdots+a_{nj}C_{nj},$$

Equivalently,

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

So you may expand along a row or along a column. The right choice is whichever one produces the cleanest minors.

To see why the column formula follows from the row formula, fix column $j$. Write $A(i|j)$ for the matrix obtained by deleting row $i$ and column $j$. The entry $a_{ij}$ becomes the entry in row $j$ of $A^T$, and deleting that row and column gives

$$(A^T)(j\mid i)=(A(i\mid j))^T$$

The two submatrices have the same determinant by transpose invariance. Therefore row-$j$ expansion of $A^T$ is

$$\det(A^T)=\sum_{i=1}^n(-1)^{j+i}a_{ij}\det((A^T)(j\mid i)) =\sum_{i=1}^n(-1)^{i+j}a_{ij}\det(A(i\mid j))$$

which equals $\det(A)$. This is the promised column-$j$ expansion.

Worked example

A column expansion with many zeros

Let

$$A= \begin{bmatrix} 1&7&0\\ 6&9&8\\ 0&1&5 \end{bmatrix}.$$

The third column has one zero, so expand along that column:

$$\det(A)= 0\cdot C_{13} +8C_{23} +5C_{33}.$$

That gives

$$\det(A) =-8 \begin{vmatrix} 1&7\\ 0&1 \end{vmatrix} +5 \begin{vmatrix} 1&7\\ 6&9 \end{vmatrix} =-8(1)+5(9-42)=-173.$$

The same answer would come from row expansion, but the chosen column makes the arithmetic shorter.

Column operations obey the same pattern

Because transpose preserves determinant, every row-operation rule has a column version.

Theorem

How column operations change determinant

Let $B$ be obtained from a square matrix $A$ by one elementary column operation.

1. Swapping two distinct columns $p$ and $q$ multiplies the determinant by $-1$.
2. Multiplying column $p$ by $\beta$ multiplies the determinant by $\beta$. For a reversible elementary operation, $\beta\neq0$.
3. Replacing column $q$ by $C_q+cC_p$, with $p\neq q$, leaves the determinant unchanged.

These are the row rules applied to $A^T$, followed by transpose invariance. The source and target columns in rule 3 must be different. The same transfer gives multilinearity in one column and the fact that two equal columns force a zero determinant. Those two properties will do the cancellation work in Cramer's rule.

Worked example

Use column operations to create zeros

Consider

$$C= \begin{bmatrix} 3&2&-1\\ 4&1&6\\ -3&-1&2 \end{bmatrix}.$$

Apply the column operations $C_1\leftarrow C_1-C_2$ and then $C_1\leftarrow C_1+C_3$, using the updated first column at each step:

$$\begin{bmatrix} 3&2&-1\\ 4&1&6\\ -3&-1&2 \end{bmatrix} \longrightarrow \begin{bmatrix} 1&2&-1\\ 3&1&6\\ -2&-1&2 \end{bmatrix}.$$

After the first step, the second step gives

$$\begin{bmatrix} 1&2&-1\\ 3&1&6\\ -2&-1&2 \end{bmatrix} \longrightarrow \begin{bmatrix} 0&2&-1\\ 9&1&6\\ 0&-1&2 \end{bmatrix}.$$

These are column-addition operations, so the determinant is unchanged. Expand along the first column:

$$\det(C)= 9(-1)^{2+1} \begin{vmatrix} 2&-1\\ -1&2 \end{vmatrix} =-9(4-1)=-27.$$

The negative cofactor sign at position $(2,1)$ is essential. Choose row or column operations according to which creates useful zeros, and use the updated matrix at each step.

Adjoint matrices package all cofactors at once

The cofactor of one entry helps in one expansion. The adjoint matrix collects all cofactors into one object.

Definition

Adjoint matrix

For an $n\times n$ matrix $A=[a_{ij}]$ with $n\ge2$, let $C_{ij}$ denote the cofactor of $a_{ij}$, and first form the cofactor matrix

$$\begin{bmatrix} C_{11}&C_{12}&\cdots&C_{1n}\\ C_{21}&C_{22}&\cdots&C_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ C_{n1}&C_{n2}&\cdots&C_{nn} \end{bmatrix}.$$

The adjoint matrix is the transpose of that cofactor matrix:

$$\operatorname{adj}(A)= \begin{bmatrix} C_{11}&C_{21}&\cdots&C_{n1}\\ C_{12}&C_{22}&\cdots&C_{n2}\\ \vdots&\vdots&\ddots&\vdots\\ C_{1n}&C_{2n}&\cdots&C_{nn} \end{bmatrix}.$$

For the $1\times1$ base case, define $\det([a])=a$ and $\operatorname{adj}([a])=[1]$. Then $[a][1]=[a]=\det([a])I_1$. The cofactor identity proof below handles $n\ge2$.

Theorem

Adjoint identity and inverse formula

For every square matrix $A$, including singular matrices,

$$A\,\operatorname{adj}(A)=\det(A)I.$$

If $\det(A)\neq0$, then $A$ is invertible and

$$A^{-1}=\frac{1}{\det(A)}\operatorname{adj}(A).$$

Proof

The diagonal and off-diagonal cases

The following proof assumes $n\ge2$; the $1\times1$ base case was defined above.

The $(i,j)$ entry of $A \operatorname{adj}(A)$ is

$$\bigl(A\operatorname{adj}(A)\bigr)_{ij}=\sum_{k=1}^n a_{ik}C_{jk}.$$

If $i=j$, this is cofactor expansion along row $i$, so it equals $\det(A)$. If $i\neq j$, form $B$ by replacing row $j$ of $A$ with row $i$. The matrix $B$ has two equal rows, hence $\det(B)=0$. Expanding $B$ along its replaced row $j$ uses exactly the cofactors $C_{jk}$ from $A$: deleting row $j$ removes the replacement. Therefore

$$0=\det(B)=\sum_{k=1}^n a_{ik}C_{jk}.$$

The diagonal entries are $\det(A)$ and every off-diagonal entry is zero. When $\det(A)\neq0$, divide by that scalar and use the square-matrix inverse criterion. The identity itself remains valid when $A$ is singular; only the inverse formula requires division.

Worked example

Recover the 2×2 inverse formula from the adjoint

Let

$$A= \begin{bmatrix} a&b\\ c&d \end{bmatrix}, \qquad \det(A)=ad-bc\neq0.$$

The cofactor matrix is

$$\begin{bmatrix} d&-c\\ -b&a \end{bmatrix},$$

so

$$\operatorname{adj}(A)= \begin{bmatrix} d&-b\\ -c&a \end{bmatrix}.$$

Therefore

$$A^{-1}= \frac{1}{ad-bc} \begin{bmatrix} d&-b\\ -c&a \end{bmatrix}.$$

The familiar inverse formula is really the adjoint identity written in the $2\times2$ case. Multiplication displays the cancellation:

$$A\operatorname{adj}(A)=\begin{bmatrix}ad-bc&0\\0&ad-bc\end{bmatrix}=(ad-bc)I_2.$$

The transpose in the adjoint is essential. If the untransposed cofactor matrix $\begin{bmatrix}d&-c\\-b&a\end{bmatrix}$ were used instead, the product would generally have entries $ad-b^2$, $ab-ac$, $cd-bd$, and $ad-c^2$, not a scalar on the diagonal with zero off-diagonal entries.

Cramer's rule solves one coordinate at a time

Theorem

Cramer's rule

Let $A\in M_n(\mathbb{R})$ satisfy $\det(A)\ne0$, and let $b\in\mathbb{R}^n$. For each $j$, let $M_j$ be the matrix obtained by replacing the $j$th column of $A$ with $b$.

If $x$ is the unique solution of

$$Ax=b,$$

then

$$x_j=\frac{\det(M_j)}{\det(A)}.$$

Each coordinate is a determinant ratio, expressing its dependence on the coefficient matrix and the right-hand side.

Proof

Fixed-column linearity isolates x_j

Write the columns of $A$ as $a_1,\ldots,a_n$. Since $\det(A)\neq0$, the system has a unique solution and

$$b=x_1a_1+\cdots+x_na_n.$$

In $M_j$, keep every column except column $j$ fixed and substitute this sum only into column $j$. By linearity in that column,

$$\det(M_j)=\sum_{k=1}^n x_k\det(a_1,\ldots,a_{j-1},a_k,a_{j+1},\ldots,a_n).$$

When $k\neq j$, the determinant has two equal columns, so that term is zero. The remaining term is $x_j \det(A)$. Hence

$$\det(M_j)=x_j\det(A), \qquad x_j=\frac{\det(M_j)}{\det(A)}.$$

The order of the columns never changes, which is why no additional sign appears.

Why replacing one column isolates one unknown

The visual below follows the determinant logic behind Cramer's rule: replace one column by the right-hand side vector, use column linearity, and watch repeated columns force the extra terms to vanish.

For $n\ge2$, the established inverse formula gives a second, compatible reading of the same coordinate formula. Since $\det(A)\ne0$, we have $\operatorname{adj}(A)=\det(A)A^{-1}$. Applying $A^{-1}$ to $Ax=b$ and then substituting this identity gives

$$\det(A)x=\operatorname{adj}(A)b, \qquad x_j=\frac{\sum_{i=1}^n C_{ij}b_i}{\det(A)}$$

The numerator is exactly $\det(M_j)$: expand $M_j$ down its replaced column $j$. Deleting that column removes $b$ and leaves the same minor as in $A$, so the cofactor attached to $b_i$ is $C_{ij}$. Thus the adjoint route and the fixed-column linearity route meet at the same signed sum. For $n=1$, write $A=[a]$ and $b=[b_1]$ with $a\ne0$; directly, $x_1=b_1/a$.

Worked example

A 3×3 adjoint and replacement determinants

Let

$$A=\begin{bmatrix}1&2&3\\1&0&1\\1&1&-1\end{bmatrix}, \qquad b=\begin{bmatrix}2\\3\\1\end{bmatrix}.$$

Expansion along the first row gives

$$\det(A)=1(-1)-2(-2)+3(1)=6.$$

The cofactor matrix is

$$\begin{bmatrix}-1&2&1\\5&-4&1\\2&2&-2\end{bmatrix}.$$

Transposing it gives

$$\operatorname{adj}(A)=\begin{bmatrix}-1&5&2\\2&-4&2\\1&1&-2\end{bmatrix}.$$

Replacing columns one, two, and three by $b$ gives

$$M_1=\begin{bmatrix}2&2&3\\3&0&1\\1&1&-1\end{bmatrix},\quad M_2=\begin{bmatrix}1&2&3\\1&3&1\\1&1&-1\end{bmatrix},\quad M_3=\begin{bmatrix}1&2&2\\1&0&3\\1&1&1\end{bmatrix}.$$

Their first-row expansions are

$$\det(M_1)=-2+8+9=15,\qquad \det(M_2)=-4+4-6=-6,\qquad \det(M_3)=-3+4+2=3.$$

Thus the solution is

$$(x_1,x_2,x_3)=\left(\frac{15}{6},\frac{-6}{6},\frac36\right) =\left(\frac52,-1,\frac12\right).$$

Substitution gives $5/2-2+3/2=2$, $5/2+1/2=3$, and $5/2-1-1/2=1$, so all three equations agree with $b$.

The numerical data also provide an independent audit of the signs and of the adjoint route. Multiplying the displayed adjoint by $b$ gives

$$\operatorname{adj}(A)b=\begin{bmatrix}15\\-6\\3\end{bmatrix}$$

so the adjoint identity predicts $x=\operatorname{adj}(A)b/\det(A)$, exactly the vector obtained from the three replacement determinants. For example, the first entry is $-1(2)+5(3)+2(1)=15$; the signs in the cofactor matrix are already included before this multiplication.

Worked example

Solve a 2×2 system with Cramer's rule

Solve

$$\begin{cases} 2x_1+x_2=5,\\ x_1+3x_2=7. \end{cases}$$

Write

$$A= \begin{bmatrix} 2&1\\ 1&3 \end{bmatrix}, \qquad b= \begin{bmatrix} 5\\ 7 \end{bmatrix}.$$

First compute

$$\det(A)=2\cdot3-1\cdot1=5.$$

Replace the first column by $b$:

$$M_1= \begin{bmatrix} 5&1\\ 7&3 \end{bmatrix}, \qquad \det(M_1)=15-7=8.$$

Replace the second column by $b$:

$$M_2= \begin{bmatrix} 2&5\\ 1&7 \end{bmatrix}, \qquad \det(M_2)=14-5=9.$$

So

$$x_1=\frac{8}{5}, \qquad x_2=\frac{9}{5}.$$

Substitution checks the result: $2(8/5)+9/5=5$ and $8/5+3(9/5)=7$.

Common mistake

Common mistake

Cramer's rule is not a universal system solver

Cramer's rule requires a square coefficient matrix and a nonzero determinant. If the system is rectangular or singular, the rule is not available. Even when it applies, it is usually less efficient than Gaussian elimination for large systems.

Counterexample mode

Zero replacement determinants do not classify singular systems

Let $A=\operatorname{diag}(1,0,0)$, a nonzero singular matrix. With $b=e_1=(1,0,0)^T$, the equations are $x_1=1$, $0=0$, and $0=0$, so the solutions are $(1,s,t)$. With $b=e_2=(0,1,0)^T$, the second equation is $0=1$, so the system is inconsistent.

Write the replacement column triples explicitly. For $b=e_1$, $(M_1)=(e_1,0,0)$, $(M_2)=(e_1,e_1,0)$, and $(M_3)=(e_1,0,e_1)$; every determinant is zero because of a zero column or repeated columns. For $b=e_2$, $(M_1)=(e_2,0,0)$, $(M_2)=(e_1,e_2,0)$, and $(M_3)=(e_1,0,e_2)$; every determinant is zero because each triple has a zero column, and $M_1$ has two zero columns. Thus all six formal ratios are $0/0$ and undefined. Require $\det(A)\ne0$ before using Cramer's rule. For a singular system, row-reduce the augmented matrix and inspect consistency and free variables.

Quick check

Checkpoint

Does transpose change the determinant of a square matrix?

State the theorem directly.

Solution · Answer

No. $\det(A^T)=\det(A)$.

Checkpoint

What column operation leaves the determinant unchanged?

Think of the column analogue of a type-III row operation.

Solution · Answer

Adding a scalar multiple of one distinct source column to another target column leaves the determinant unchanged.

Checkpoint

When may Cramer's rule be used?

Identify the structural hypotheses on A.

Solution · Answer

When the coefficient matrix is square and invertible, equivalently when its determinant is nonzero.

Exercises

Checkpoint

Use a column expansion to compute $\det\begin{bmatrix}1&0&2\\3&4&5\\0&0&6\end{bmatrix}$.

Choose the column with the most zeros.

Solution · Guided solution

Expand along the second column:

$$\det= 4(-1)^{2+2} \begin{vmatrix} 1&2\\ 0&6 \end{vmatrix} =4(6)=24.$$

Checkpoint

For $A=\begin{bmatrix}1&2\\3&4\end{bmatrix}$, write down $\operatorname{adj}(A)$.

Compute the four cofactors first, then transpose the cofactor matrix.

Solution · Guided solution

The cofactors are $C_{11}=4$, $C_{12}=-3$, $C_{21}=-2$, and $C_{22}=1$. Hence

$$\operatorname{adj}(A)= \begin{bmatrix} 4&-2\\ -3&1 \end{bmatrix}.$$

Checkpoint

Use Cramer's rule to find x_1 for the system $x_1+x_2=3$, $2x_1-x_2=0$.

You only need $\det(A)$ and $\det(M_1)$.

Solution · Guided solution

Here

$$A= \begin{bmatrix} 1&1\\ 2&-1 \end{bmatrix}, \qquad b= \begin{bmatrix} 3\\ 0 \end{bmatrix}.$$

Then

$$\det(A)=-1-2=-3, \qquad M_1= \begin{bmatrix} 3&1\\ 0&-1 \end{bmatrix}, \qquad \det(M_1)=-3.$$

So

$$x_1=\frac{\det(M_1)}{\det(A)}=1.$$

Related notes

Return to 7.2 Row operations, products, and invertibility if the row-operation bookkeeping is still shaky.

Keep 3.3 Transpose, symmetric, and skew-symmetric matrices nearby, because the transpose theorem here extends that earlier structural chapter.

For system language, connect this note back to 1.1 Equations and solution sets and 2.3 Gaussian elimination and RREF.