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 ith row of A is zero and the ith 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 ith row of A is zero while the ith 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 ith row of A by the jth column of X; since the ith row of A is zero, we have a contradiction. Thus AX = C has no solutions.

Suppose now that for all i, the ith row of A is zero only if the ith 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.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: