Invertible matrices

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.

Finite basis existence and extension, without a counting assumption

Let $V$ be a real vector space supplied with a finite spanning list $t_1,\ldots,t_N$. First prove that every independent list $u_1,\ldots,u_k$ has length at most $N$. After $j$ insertions, maintain a spanning list consisting of $u_1,\ldots,u_j$ and $N-j$ surviving old vectors. Expand $u_{j+1}$ in this list. Some coefficient on a surviving old vector is nonzero; otherwise $u_{j+1}$ would be in the span of the earlier $u_i$, contradicting independence. Solve for that old vector and replace it by $u_{j+1}$. The new list spans the same space and keeps every earlier insertion. If $k>N$, after $N$ steps the first $N$ independent vectors already span $V$, contradicting independence of $u_{N+1}$. This proves the bound, including $N=0$.

Every subspace $W$ has a finite basis. Start with the empty independent list. If its current span is not $W$, choose one vector of $W$ outside that span. A relation with nonzero coefficient on the new vector would express it in the old span, so the enlarged list remains independent. The proved bound permits at most $N$ additions; therefore the process stops with an independent spanning list for $W$. If $W=\{0\}$, it stops immediately with the empty basis. Starting instead with any given independent list in $W$ proves that list extends to a basis of $W$. Only a bounded finite selection is used. Finally, if two bases have sizes $p,q$, use each as the finite spanning list in the bound to obtain $p\le q$ and $q\le p$. Thus basis size, called dimension, is well-defined. This supplies the existence, extension and dimension facts used in rank–nullity.

A square matrix can send different inputs to the same output, or leave some outputs unreachable. An inverse must undo its action completely: every output must come from exactly one input. This requirement connects reversibility to the solution sets of $Ax=b$. Entries are real unless another field is specified.

Before you start

Use matrix multiplication in its given order and recall that each elementary row operation is reversible. A system $Ax=b$ has a unique solution exactly when it is consistent and every variable column is a pivot column after reduction. Invertibility will guarantee this for every right-hand side of the appropriate dimension.

Left and right inverses

Definition

Left inverse and right inverse

Let $A$ be a $p \times q$ matrix.

• A $q \times p$ matrix $H$ is a left inverse of $A$ if $HA = I_q$.
• A $q \times p$ matrix $G$ is a right inverse of $A$ if $AG = I_p$.

For rectangular matrices, a left inverse or a right inverse can exist alone. If both exist, however, they must coincide. The square case will give the stronger conclusion that either one-sided inverse already guarantees the other.

Definition

Invertible matrix

Let $A$ be a $p \times p$ square matrix. We say that $A$ is invertible if there exists a $p \times p$ matrix $B$ such that

$$BA = AB = I_p.$$

The matrix $B$ is called the inverse of $A$, and we write $B = A^{-1}$.

Theorem

The inverse is unique

Let $A$ be $p\times q$ and let $B,C$ be $q\times p$. If $B$ is a left inverse of $A$ and $C$ is a right inverse, then $B=C$. In particular, an invertible square matrix has exactly one inverse.

Proof

Why the inverse is unique

The assumptions are $BA=I_q$ and $AC=I_p$. Associativity gives

$$B=BI_p=B(AC)=(BA)C=I_qC=C.$$

No factors were interchanged. For an invertible square matrix, any two inverses satisfy these hypotheses, so they coincide.

What invertibility means

The equations defining an inverse restore every input vector. Diagonal matrices make that action especially transparent.

Worked example

A diagonal matrix is easy to invert

Let

$$D = \operatorname{diag}(2, -1, 3).$$

Then

$$D^{-1} = \operatorname{diag}\left(\tfrac{1}{2}, -1, \tfrac{1}{3}\right).$$

This works because each diagonal entry is replaced by its reciprocal, and the off-diagonal zeros stay zero. Multiplying $D$ by $D^{-1}$ gives $I_3$.

Equivalent formulations

Theorem

Equivalent ways to recognize invertibility

Let $A$ be a real $p\times p$ matrix. The following conditions are equivalent:

1. $A$ is invertible.
2. $A$ is row-equivalent to $I_p$.
3. $A$ is a product of elementary row-operation matrices of order $p$.
4. $A$ has a left inverse.
5. $A$ has a right inverse.
6. $A$ is nonsingular: $Ax=0$ has only the zero solution.
7. For every $b\in\mathbb R^p$, the system $Ax=b$ is consistent.
8. For every $b\in\mathbb R^p$, the system $Ax=b$ has exactly one solution.

Equivalently, the columns of $A$ are linearly independent, or they span $\mathbb R^p$. When these conditions hold, the unique solution is $A^{-1}b$.

Proof

Where the square hypothesis enters the equivalence proof

A left inverse $H$ forces the homogeneous solution to be zero: if $Ax=0$, then $x=HAx=0$. Conversely, suppose the homogeneous system has only the zero solution. In any RREF of $A$, a free variable would produce a nonzero homogeneous solution. Thus every column has a pivot. Because $A$ is square, there are also exactly $p$ pivot rows, and the RREF is $I_p$.

If a row-operation product $E$ satisfies $EA=I_p$, the reverse chain shows that $E$ is invertible and $A=E^{-1}$. Hence $A$ is invertible and is itself a product of elementary matrices. Conversely, any such product is invertible, and an inverse is in particular a left inverse. This connects conditions 1–4 and 6 without assuming uniqueness of RREF.

Now suppose $AG=I_p$. Then $A$ is a left inverse of the square matrix $G$. The already proved left-inverse criterion makes $G$ invertible, and $A=A(GG^{-1})=(AG)G^{-1}=G^{-1}$ is invertible. This proves the right-inverse criterion without silently reversing a product.

If every $Ax=b$ is consistent, choose solutions $u_j$ of $Au_j=e_j$, where $e_j$ is column $j$ of $I_p$. Their matrix $U=[u_1\ \cdots\ u_p]$ satisfies $AU=I_p$, so the right-inverse criterion applies. Finally, when $A$ is invertible, $A(A^{-1}b)=b$ proves existence, and any solution $x$ satisfies $x=A^{-1}Ax=A^{-1}b$, proving uniqueness. Uniqueness for every right-hand side implies consistency for every right-hand side.

The column statements are translations: independence means that $Ax=0$ has only the zero coefficient vector, and spanning means that every $b$ has a representation $Ax=b$. Thus no additional assumption about the columns is being introduced.

Row reduction and the inverse

Each elementary row-operation matrix is invertible; its inverse encodes the reverse operation, as proved in 3.5 Elementary row-operation matrices. If the chronological operations have matrices $E_1,\ldots,E_k$, their combined left multiplier is $E=E_k\cdots E_1$.

Apply every operation across the entire augmented matrix. Then

$$E[A\mid I_p]=[EA\mid E].$$

If the left block becomes $I_p$, then $EA=I_p$. Since $E$ is invertible, $A=E^{-1}$ and the right block $E$ is $A^{-1}$. If reduction leaves a missing pivot in the left block, the square matrix fails the equivalent conditions above. The method tests invertibility as well as computing an inverse; a complicated right block cannot compensate for a missing left pivot.

How to use the invertibility dictionary

Choose the criterion matching the given evidence: pivots, a one-sided identity, a nonzero null-space vector, or information about all right-hand sides.

Worked example

A nonzero null-space vector proves non-invertibility

Suppose $A$ is a square matrix and

$$v = \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix} \ne 0, \qquad Av = 0.$$

Then $A$ cannot be invertible. Indeed, if $A^{-1}$ existed, multiplying $Av = 0$ on the left by $A^{-1}$ would give

$$A^{-1}Av = A^{-1}0.$$

The left side is $v$, while the right side is $0$. This would force $v = 0$, contradicting the given vector. Therefore the existence of one nonzero solution of $Ax = 0$ already proves that $A$ is singular.

Worked example

Use an inverse to solve a system

Suppose

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

If $Ax = b$, then multiply both sides by $A^{-1}$:

$$x = A^{-1}b = \begin{bmatrix} 2 & -1 \\ 0 & 3 \end{bmatrix} \begin{bmatrix} 5 \\ -1 \end{bmatrix} = \begin{bmatrix} 11 \\ -3 \end{bmatrix}.$$

The inverse is not just a symbol for undoing $A$; it is an explicit formula for the unique solution.

Row-equivalence through invertible matrices

Theorem

Row-equivalence is left multiplication by an invertible matrix

Suppose $A$ and $B$ are matrices with $p$ rows. Then the following are equivalent:

• $A$ and $B$ are row-equivalent.
• There exists an invertible $p \times p$ matrix $G$ such that

$$B = GA.$$

Moreover, once $B = GA$, we also have

$$A = G^{-1}B.$$

A row-operation chain supplies such a product $G$. Conversely, the dictionary expresses any invertible $G$ as a product of elementary matrices, so $GA$ is obtained from $A$ by those row operations. Multiplying by $G^{-1}$ recovers $A$.

Worked example

Reading a row-equivalence as one matrix equality

Let

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

The matrix $G$ is the row-operation matrix for the move

$$R_2 \leftarrow R_2 - R_1.$$

So

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

If we call this new matrix $B$, then $B = GA$. That single equation records the entire row operation. Since $G$ is invertible, $A$ and $B$ are row-equivalent.

Theorem

Row operations preserve linear relations among corresponding columns

Let $A$ and $B$ be row-equivalent $p \times q$ matrices, and write their columns as

$$A = [a_1 \; a_2 \; \cdots \; a_q], \qquad B = [b_1 \; b_2 \; \cdots \; b_q].$$

If

$$a_j = \alpha_1 a_{k_1} + \alpha_2 a_{k_2} + \cdots + \alpha_n a_{k_n},$$

then

$$b_j = \alpha_1 b_{k_1} + \alpha_2 b_{k_2} + \cdots + \alpha_n b_{k_n}.$$

In particular, linear dependence and linear independence among corresponding columns are preserved by row-equivalence.

Multiplying by $G$ carries each relation forward; multiplying by $G^{-1}$ recovers it. Thus the same coefficient relations hold in both directions, which also proves preservation of dependence and independence. The columns themselves generally change. The full RREF uniqueness argument and its role in rank are developed in 5.2 Rank and uniqueness of RREF.

Products and inverse order

Theorem

A square product is invertible exactly when its factors are

Let $A,B$ be real $p\times p$ matrices. Then $AB$ is invertible if and only if both $A$ and $B$ are invertible. In that case,

$$(AB)^{-1}=B^{-1}A^{-1}.$$

Proof

Construct the inverse before using its name

First assume the factors are invertible and set $C=B^{-1}A^{-1}$. Check both sides using associativity:

$$(AB)C=A(BB^{-1})A^{-1}=I_p,\qquad C(AB)=B^{-1}(A^{-1}A)B=I_p.$$

Only now may we conclude that $C=(AB)^{-1}$. The reversed order places the inverse pairs next to each other; no commutativity is used.

For the converse, assume $AB$ is invertible and write $C=(AB)^{-1}$. We cannot yet use $A^{-1}$ or $B^{-1}$. Instead,

$$A(BC)=I_p,\qquad (CA)B=I_p.$$

Thus $A$ has a right inverse and $B$ has a left inverse. Both factors are square of the same order, so the previously proved one-sided criteria make them invertible. This use of the dictionary is essential to the converse.

By induction, a finite product of square matrices of the same order is invertible exactly when every factor is invertible, and

$$(A_1\cdots A_k)^{-1}=A_k^{-1}\cdots A_1^{-1}.$$

Why the transpose also matters

Theorem

Transpose, scalar multiples, and powers

If $A$ is invertible, then $(A^{-1})^{-1}=A$ and $(A^T)^{-1}=(A^{-1})^T$. For a nonzero real scalar $c$, $(cA)^{-1}=c^{-1}A^{-1}$.

Every integer power $A^n$ is invertible, with $(A^n)^{-1}=(A^{-1})^n$. Here $A^0=I_p$, and for a positive integer $m$, $A^{-m}=(A^{-1})^m$.

The transpose formula follows by transposing both inverse identities, which reverses their factor order. The scalar formula follows by cancelling $c$ and $c^{-1}$ in both products. Positive powers follow from the product theorem; negative powers apply it to $A^{-1}$, and the zero power is the identity. For a positive integer $n$, invertibility of $A^n$ also implies invertibility of $A$. That converse is false for $n=0$, since $A^0=I_p$ even for singular square $A$.

Products that equal the identity

Theorem

A one-sided identity is enough in the square case

Let $P$ and $Q$ be square matrices of the same size. If

$$PQ=I,$$

then both $P$ and $Q$ are invertible, and

$$Q=P^{-1},\qquad QP=I.$$

Worked example

Cyclic identities from $ABCD=I$

Suppose $A,B,C,D$ are $5 \times 5$ matrices and

$$ABCD=I_5.$$

Group the product as

$$(ABC)D=I_5.$$

By the one-sided identity theorem, $ABC$ and $D$ are inverses of each other. Therefore

$$DABC=I_5.$$

Next group the same original product cyclically:

$$(DAB)C=I_5 \qquad\text{and}\qquad (CDA)B=I_5,$$

after using the already justified cyclic identities. This gives

$$CDAB=I_5, \qquad BCDA=I_5.$$

So $BCDA$, $CDAB$, and $DABC$ are forced to equal $I_5$. Arbitrary reorderings such as $DCBA$ or $DBAC$ are not forced by $ABCD=I_5$; matrix multiplication still does not commute.

Compute an inverse by row reduction

Worked example

Find an inverse by row reduction

Let

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

Start from $[A\mid I_2]$:

$$\left[\begin{array}{cc|cc} 1 & 2 & 1 & 0 \\ 3 & 5 & 0 & 1 \end{array}\right].$$

Eliminate the entry below the first pivot:

$$\left[\begin{array}{cc|cc} 1 & 2 & 1 & 0 \\ 0 & -1 & -3 & 1 \end{array}\right].$$

Now scale the second row and clear the entry above the second pivot:

$$\left[\begin{array}{cc|cc} 1 & 0 & -5 & 2 \\ 0 & 1 & 3 & -1 \end{array}\right].$$

So

$$A^{-1} = \begin{bmatrix} -5 & 2 \\ 3 & -1 \end{bmatrix}.$$

A family of inverse matrices

Worked example

A parameterized inverse from row reduction

For a real number $\alpha$, let

$$A_\alpha = \begin{bmatrix} 1 & 2 & 1 & 2 \\ 1 & 3 & 1 & 2 \\ 0 & 0 & 1 & \alpha \\ 1 & 2 & 1 & 3 \end{bmatrix}.$$

Row-reducing the augmented matrix $[A_\alpha \mid I_4]$ gives

$$\left[\begin{array}{cccc|cccc} 1 & 0 & 0 & 0 & 5-\alpha & -2 & -1 & \alpha-2 \\ 0 & 1 & 0 & 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & \alpha & 0 & 1 & -\alpha \\ 0 & 0 & 0 & 1 & -1 & 0 & 0 & 1 \end{array}\right].$$

Since the left block is $I_4$ for every real $\alpha$, the matrix $A_\alpha$ is invertible for every real $\alpha$, and

$$A_\alpha^{-1} = \begin{bmatrix} 5-\alpha & -2 & -1 & \alpha-2 \\ -1 & 1 & 0 & 0 \\ \alpha & 0 & 1 & -\alpha \\ -1 & 0 & 0 & 1 \end{bmatrix}.$$

Notice what this conclusion does and does not say. The parameter remains in the inverse; it is not a value to be solved for. The row reduction has shown that no value of $\alpha$ creates a missing pivot in the left block.

Common mistake

Do not treat every parameter as a restriction

Sometimes a parameter appears because the answer is a family of inverses, not because the matrix fails for special values. The restriction comes from a missing pivot or an illegal division by zero, not from the mere presence of a symbol.

Reading supplied row-reduction tables

Worked example

An inverse pair and a transposed system

Suppose a reduction table shows that $[A \mid I_4]$ is row-equivalent to $[I_4 \mid D]$, where

$$D= \begin{bmatrix} 3 & -2 & 3 & -2 \\ 0 & 1 & -2 & 1 \\ -3 & 1 & -2 & 2 \\ 1 & 0 & 1 & -1 \end{bmatrix}.$$

Then the row-reduction result itself already says

$$A^{-1}=D.$$

The corresponding coefficient matrix is

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

Direct multiplication gives $AD=I_4$, which verifies this inverse pair. Now let

$$g= \begin{bmatrix} 1 \\ 0 \\ 3 \\ 0 \end{bmatrix}.$$

To solve $A^t x=g$, do not row-reduce again from the beginning. Since $A$ is invertible, $A^t$ is also invertible and

$$(A^t)^{-1}=(A^{-1})^t=D^t.$$

Therefore

$$x=(A^t)^{-1}g=D^t g = \begin{bmatrix} -6 \\ 1 \\ -3 \\ 4 \end{bmatrix}.$$

The computation is short because the reduction table has already done the hard work.

Worked example

Four inverse computations read by pivot columns

For each matrix below, the method is the same: row-reduce $[A \mid I_4]$, look only at the pivot pattern of the left block first, and read the inverse from the right block only if the left block becomes $I_4$.

Case (a). For

$$A_1= \begin{bmatrix} 1 & 0 & 3 & 3 \\ 2 & 1 & 2 & 3 \\ -1 & 3 & 0 & 3 \\ 4 & 2 & 2 & 4 \end{bmatrix},$$

one echelon stage has left block

$$A_1^\sharp= \begin{bmatrix} 1 & 0 & 3 & 3 \\ 0 & 1 & -4 & -3 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

There is no pivot in the fourth column. Hence $A_1$ is not invertible.

Case (b). Take $A_2=A$ from the preceding inverse-pair example. Its reduction reaches $[I_4 \mid D]$, so all four columns have pivots and $A_2^{-1}=D$. The same matrix used there to solve the transposed system provides an invertible case here.

Case (c). For

$$A_3= \begin{bmatrix} 1 & 2 & -1 & 30 \\ 3 & 2 & 0 & 15 \\ 0 & 1 & 3 & 15 \\ 1 & 1 & 1 & 10 \end{bmatrix},$$

one echelon stage has left block

$$A_3^\sharp= \begin{bmatrix} 1 & 2 & -1 & 30 \\ 0 & 1 & 3 & 15 \\ 0 & 0 & 5 & -5 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

Again a pivot column is missing, so $A_3$ is not invertible.

Case (d). For

$$A_4= \begin{bmatrix} 1 & 1 & 2 & 1 \\ 2 & 3 & 4 & 1 \\ 3 & 3 & 3 & 1 \\ 1 & 2 & 3 & 1 \end{bmatrix},$$

the reduction reaches $[I_4 \mid A_4^{-1}]$, with

$$A_4^{-1}= \begin{bmatrix} 1 & 1 & 0 & -2 \\ -2 & -2 & 1 & 3 \\ 1 & 2 & -1 & -2 \\ 0 & -3 & 1 & 3 \end{bmatrix}.$$

The identity left block certifies invertibility in cases (b) and (d). The missing pivots in cases (a) and (c) rule it out, regardless of the entries in the right block.

Worked example

A final identity block controls the whole chain

Suppose a row-operation chain carries $[A \mid I_5]$ through an intermediate matrix $[B \mid C]$ and finally to $[D \mid E]$. After the last few operations, the final augmented matrix is

$$[D \mid E] = \left[ \begin{array}{ccccc|ccccc} 1 & 0 & 0 & 0 & 0 & 1 & 0 & -2 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 9 & 1 & -18 & -3 & -2 \\ 0 & 0 & 1 & 0 & 0 & -6 & 2 & 11 & 2 & 0 \\ 0 & 0 & 0 & 1 & 0 & -3 & 0 & 6 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & -6 & 0 & 12 & 2 & 1 \end{array} \right].$$

The left block is $I_5$, so $D=I_5$ and

$$A^{-1}=E= \begin{bmatrix} 1 & 0 & -2 & 0 & 0 \\ 9 & 1 & -18 & -3 & -2 \\ -6 & 2 & 11 & 2 & 0 \\ -3 & 0 & 6 & 1 & 0 \\ -6 & 0 & 12 & 2 & 1 \end{bmatrix}.$$

It follows immediately that $A^t$ is invertible and

$$(A^t)^{-1}=E^t = \begin{bmatrix} 1 & 9 & -6 & -3 & -6 \\ 0 & 1 & 2 & 0 & 0 \\ -2 & -18 & 11 & 6 & 12 \\ 0 & -3 & 2 & 1 & 2 \\ 0 & -2 & 0 & 0 & 1 \end{bmatrix}.$$

The same chain can also be read as one left multiplication. Let $H$ be the product of all row-operation matrices in the chain. Since $HA=I_5$ and $HI_5=E$, we have $H=A^{-1}$. Therefore, if the same row operations carry $F+I_5$ to $A^3+3A+I_5$, then

$$A^3+3A+I_5=A^{-1}(F+I_5).$$

Multiplying by $A$ on the left gives

$$F+I_5=A(A^3+3A+I_5)=A^4+3A^2+A,$$

so

$$F=A^4+3A^2+A-I_5.$$

The same row-operation chain acts on every matrix by the same left multiplier $H=A^{-1}$. This is why the numerical reduction also determines the equation for $F$.

Prove or disprove invertibility without determinants

Worked example

A vector identity that proves invertibility

Suppose $A$ is a $7 \times 7$ matrix and

$$A^2x = Ax + x$$

for every vector $x \in \mathbb R^7$. Move the terms involving $A$ to the left:

$$(A^2-A)x = x \qquad\text{for every }x.$$

Since $A^2-A=(A-I_7)A$, this says

$$((A-I_7)A)x = I_7x \qquad\text{for every }x.$$

Two matrices that agree on every vector are the same matrix, so

$$(A-I_7)A = I_7.$$

Thus $A-I_7$ is a left inverse of $A$. Because $A$ is square, a one-sided identity is enough: $A$ is invertible, and its inverse is $A-I_7$.

Worked example

A contradiction proof for non-invertibility

Suppose $A$ and $B$ are distinct $6 \times 6$ matrices, and

$$A^3=B^3, \qquad A^2B=B^2A.$$

We prove that $A^2+B^2$ is not invertible. Let

$$C=A^2+B^2.$$

First compare $CB$ and $CA$:

$$CB=(A^2+B^2)B=A^2B+B^3,$$

while

$$CA=(A^2+B^2)A=A^3+B^2A.$$

Using the assumptions $A^2B=B^2A$ and $B^3=A^3$, we obtain

$$CB=CA.$$

If $C$ were invertible, multiplying by $C^{-1}$ on the left would give $B=A$, contradicting the assumption that $A$ and $B$ are distinct. Therefore $C=A^2+B^2$ is not invertible.

Common mistakes

Common mistake

Do not confuse one-sided inverses in the rectangular case

For a non-square matrix, a left inverse need not come with a right inverse, and a right inverse need not come with a left inverse. If both exist, they coincide. For a square matrix, the equivalence theorem proves that either one-sided inverse guarantees a unique two-sided inverse.

Common mistake

Do not guess invertibility from appearance

A matrix can look simple and still fail to be invertible. The correct test is to row-reduce it, or to use one of the equivalent conditions above.

Common mistake

Do not permute factors without justification

From $ABCD=I$, it is legitimate to derive certain cyclic identities such as $DABC=I$ by using inverse theory. It is not legitimate to rearrange the factors as if $A,B,C,D$ commute.

Quick checks

Checkpoint

If $A$ is invertible, what is $A^{-1}A$?

Use the defining property of an inverse.

Solution · Answer

It is $I_p$.

Checkpoint

If $A$ is invertible, can the homogeneous system $Ax = 0$ have a nonzero solution?

Use the unique-solution statement.

Solution · Answer

No. Since $Ax = b$ has the unique solution $x = A^{-1}b$, the homogeneous case $b = 0$ has only the trivial solution $x = 0$.

Checkpoint

If $A$ is invertible, is $A^t$ invertible?

Use the transpose rule above.

Solution · Answer

Yes. $A^t$ is invertible, and $(A^t)^{-1} = (A^{-1})^t$.

Checkpoint

If $B = GA$ with $G$ invertible and the columns of $A$ satisfy $a_3 = 2a_1 - a_2$, what relation must hold among the columns of $B$?

Keep the same coefficients and use $b_j = Ga_j$.

Solution · Answer

The corresponding columns of $B$ satisfy

$$b_3 = 2b_1 - b_2.$$

Row-equivalence changes the columns themselves, but not the coefficient pattern in a linear relation.

Checkpoint

Suppose $A,B,C,D$ are square matrices and $ABCD=I$. Which cyclic identity is forced: $DABC=I$ or $DCBA=I$?

Group the original product as $(ABC)D=I$.

Solution · Answer

$DABC=I$ is forced. Since $(ABC)D=I$, the square one-sided identity theorem implies that $D$ is the inverse of $ABC$, so $D(ABC)=I$. The equality $DCBA=I$ would reverse the order of the factors and is not forced in general.

Checkpoint

In the parameterized inverse above, what is the $(1,4)$ entry of $A_\alpha^{-1}$ when $\alpha=3$?

Substitute $\alpha=3$ into the first row, fourth column.

Solution · Answer

The $(1,4)$ entry is $\alpha-2$, so when $\alpha=3$ it equals $1$.

Checkpoint

If $A^2x=Ax+x$ for every vector $x$, which matrix acts as the inverse of $A$?

Move all terms to one side and look for a factorization involving $A$.

Solution · Answer

The inverse is $A-I$. Indeed, the vector identity gives $(A-I)A=I$; for square matrices, this one-sided identity is enough to conclude that $A$ is invertible.

Checkpoint

If row operations transform $[A \mid I_p]$ into $[I_p \mid D]$, what is $D$?

Read the right block only after confirming the left block is the identity.

Solution · Answer

$D=A^{-1}$. The same row operations that turn $A$ into $I_p$ turn $I_p$ into the inverse of $A$.

Checkpoint

Row operations take $[A\mid I_p]$ to $[I_p\mid E]$, where $A$ is square. Explain why $AE=I_p$ follows as well as $EA=I_p$.

Distinguish what the row-operation product gives directly from what the square one-sided inverse theorem adds.

Solution · Answer

If $H$ is the product of the elementary matrices, the two blocks give $HA=I_p$ and $HI_p=E$. Hence $H=E$ and $EA=I_p$ directly. Because $A$ and $E$ are square of the same order, a left inverse is also a right inverse. Thus $E=A^{-1}$ and $AE=I_p$. The square hypothesis is essential to this last implication.

Exercise

Checkpoint

Suppose $A$ is invertible and $AB = I_p$. Prove that $B = A^{-1}$.

Use the fact that the inverse of $A$ is unique.

Solution · Guided solution

Since $A$ is invertible, it has an inverse $A^{-1}$. Multiply the equation $AB = I_p$ on the left by $A^{-1}$:

$$A^{-1}(AB) = A^{-1}I_p.$$

By associativity,

$$(A^{-1}A)B = A^{-1}.$$

Because $A^{-1}A = I_p$, this becomes

$$B = A^{-1}.$$

So any right inverse of an invertible square matrix must be the inverse itself.

Checkpoint

Suppose $(A-B)A=I$ for square matrices $A$ and $B$. Prove that $A$ and $B$ commute.

First use the square one-sided identity theorem, then expand $AB-BA$.

Solution · Guided solution

Since $(A-B)A=I$, the square one-sided identity theorem gives

$$A(A-B)=I.$$

Now compute the commutator:

$$AB-BA = AB-A^2+A^2-BA.$$

Regroup the two parts:

$$AB-A^2 = A(B-A) = -A(A-B),$$

and

$$A^2-BA = (A-B)A.$$

Therefore

$$AB-BA = -A(A-B)+(A-B)A = -I+I=0.$$

So $AB=BA$, which means $A$ and $B$ commute.

Related notes

This page depends especially on 2.3 Gaussian elimination and RREF, 3.2 Matrix multiplication, identity matrices, and linear systems, and 3.3 Transpose, symmetric, and skew-symmetric matrices.

The connection between a zero null space and uniqueness is developed in 4.1 Homogeneous systems and null space.