# How to determine the transition matrices when doing Gaussian elimination?

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?

• Your notation is incorrect. Row reducing doesn't give you the same matrix, so if $A = \pmatrix{2&3\\1&2}$, then we cannot say $A = \pmatrix{1&\frac 32 \\ 0& \frac 12}$. However, $A$ can be row-reduced to this latter form. – Omnomnomnom Jun 1 '15 at 16:47
• @Omnomnomnom Yes, you are right, I changed. They are different matrices but when solving a system of equations they produce the same results, or they are equivalent, no? – nbro Jun 1 '15 at 16:49
• The matrices are related in some way. However, consider the following analogy: if we want to solve the equation $$\frac 2{11}x = 4$$ we may rewrite the equation as $$2 x = 44$$ however, $2$ and $\frac 2{11}$ are certainly not the same number. – Omnomnomnom Jun 1 '15 at 16:53
• I think that if you can reduce one matrix to another, then the two matrices are called "row-equivalent". There is a different notion called "equivalence" which is slightly more general. – Omnomnomnom Jun 1 '15 at 16:54

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}$$

• Does this answer your question? Let me know if there's anything you'd like for me to elaborate on further. – Omnomnomnom Jun 1 '15 at 17:22
• This is a good example. But I have seen a general form for finding the elementary or transition matrices. For example, usually the first transition matrix is $E_{21}\left(\frac{-a_{21}}{a_{11}}\right)$, which makes sense, but it is hard to visualize how the rest of the transition matrices come out... – nbro Jun 1 '15 at 18:15
• Again, find the transition matrix by applying the operation to the identity matrix. – Omnomnomnom Jun 1 '15 at 18:41

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.