How to determine the transition matrices when doing Gaussian elimination?

Question

Guassian elimnation can be done by swapping or adding rows, and by multiplying rows by scalars, etc. We use it to bring for example our original matrix to an upper triangular matrix, so that we can easily find the solutions to a system of equations (for example by doing backward substitution). Of course we can use Gaussian elimination for other purposes.

Now, I am used to this method, but I know that this method can be represented as a multiplication of transition matrices by our original matrix and by the vector on the right side of the equals sign.

For example, suppose we have the following matrix:

$$A = \left(\begin{matrix} 2 & 3 \\ 1 & 2\end{matrix}\right)$$

Using the easiest human method described at the beginning of this question, to reduce $A$ to an upper triangular matrix, we can for example multiply the first row by $\frac{1}{2}$ and then add $-1$ times the resulting row to the second row, and we obtain:

$$A' = \left(\begin{matrix} 1 & \frac{3}{2} \\ 1 & 2\end{matrix}\right)$$

$$A'' = \left(\begin{matrix} 1 & \frac{3}{2} \\ 0 & \frac{1}{2}\end{matrix}\right)$$

Now, my question are:

• How is this in general translated to the Guassian elimination using transition matrices? Or what is the relation between the method I am used to and the method multiplying by transition matrices?

• How do in general we find these transition matrices?

• Why does the method that uses the multiplication by transition matrices also work?

Answer 1

The process of row-reduction corresponds to multiplication on the left by a (non-singular) matrix. The matrices corresponding to a single row-operation are referred to as elementary matrices (which is what I think you mean by a "transition matrix").

If we want to encode a row-operation as an elementary matrix, we can do so by performing the desired row-operation to the identity matrix. For example, suppose we want to subtract $1/2$ times the first row from the second row (and make that the new second row). To encode this as an elementary matrix, we start with the identity matrix, $$ \pmatrix{1&0\\0&1} $$ and perform the desired operation on the identity matrix. Our elementary matrix $E$ is then given by $$ E = \pmatrix{1 &0\\-1/2&1} $$ We then have $$ EA = \pmatrix{1 &0\\-1/2&1} \pmatrix{2&3\\1&2} = \pmatrix{2&3\\0&1/2} $$

Answer 2

All your transition matrices (elementary matrices) can be obtained by the identity matrix changing some row. As an example: $$ H_1(k)= \begin{bmatrix} k&0\\0&1 \end{bmatrix} $$ left multiplied by a $2\times 2$ matrix multiplies the elemnetns of the first row by $k$. Right multiplied multiplies the elemnetns of the first column by $k$.

The matrix $$ H_{12}(k)= \begin{bmatrix} 1&0\\k&1 \end{bmatrix} $$ multiplied left add the first row multiplied by $k$ to the second row, and multiplied right add the secon column multiplied by $k$ to the first column.

The matrix $$ H_{12}= \begin{bmatrix} 0&1\\1&0 \end{bmatrix} $$ exchange rows or column.

And this are all elementary transformation of a $2\times2$ matrix.

You can extend easely all this to $n\times n$ matrices.