Solving linear matrix equations

Let $A$ and $C$ be matrices (over a field) having dimension $n \times k$ and $n \times m$, respectively, such that $A$ is in reduced row echelon form. Compute the solutions of the matrix equation $AX = C$. In particular, note the following.

1. If, for some $i$, the $i$th row of $A$ is zero and the $i$th row of $C$ is nonzero, then no solution $X$ exists.
2. Every solution to $AX = C$ may be constructed by choosing the rows of $X$ corresponding to nonpivotal columns of $A$ arbitrarily, as the remaining rows are then determined uniquely.

Use this result to characterize the solutions of $AX = C$ when $A$ is not in reduced row echelon form.

Suppose that for some $i$, the $i$th row of $A$ is zero while the $i$th row of $C$ is nonzero. Suppose $X$ is a solution to the equation $AX = C$. Choose $j$ such that the $(i,j)$ entry of $C$ is nonzero. (This exists by our hypothesis.) By the definition of matrix multiplication, this entry is obtained by multiplying the $i$th row of $A$ by the $j$th column of $X$; since the $i$th row of $A$ is zero, we have a contradiction. Thus $AX = C$ has no solutions.

Suppose now that for all $i$, the $i$th row of $A$ is zero only if the $i$th row of $C$ is also zero. We will now construct all the solutions of the equation $AX = C$ recursively. Note that if $A = 0$, then by the previous argument, $AX = C$ has no solution if $C \neq 0$. We assume now that $A \neq 0$.

For the base case, suppose $A = [0 | 1 | V]$ has one row. Let $X_1$ and $X_3$ be arbitrary matrices (so that dimensions work) and let $X_2 = C - VX_3$. Letting $X_0 = \left[ \begin{array}{c} X_1 \\ \hline X_2 \\ \hline X_3 \end{array} \right]$, we see that $AX_0 = C$. Conversely, if $X_0$ is any solution to this equation, we see that $X_2$ has this form.

For the inductive step, suppose $A = \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & A_\prime \end{array} \right]$ and write $C = \left[ \begin{array}{c} C_1 \\ \hline C_2 \end{array} \right]$. Choose $X_1$ arbitrarily (so that the dimensions work), let $X_3$ be any solution of the equation $A^\prime X = C_2$ and let $X_2 = C_1 - VX_3$. Again letting $X_0 = \left[ \begin{array}{c} X_1 \\ \hline X_2 \\ \hline X_3 \end{array} \right]$, we see that $AX_0 = C$. Conversely, if $X_0$ is any such solution, then $X_2$ has this form.

Now let $A$ and $C$ be arbitrary matrices (so that dimensions work). By this previous exercise, $A$ is row equivalent to a matrix in reduced row echelon form. That is, there exists a reduced row echelon matrix $A_2$ and an invertible matrix $P$ such that $PA = A_2$. Now $A = P^{-1}A_2$, so that $AX = C$ if and only if $A_2X = PC$.

Note that this allows us to solve arbitrary “linear equations in one variable” $AX + C = 0$ over matrices. A similar proof involving column equivalence (rather than row equivalence) could be used to give an analogous solution for linear equations of the form $XA + C = 0$. In the future, we will see how canonical forms of matrices can be used to find matrix solutions to polynomial equations of higher degree.