# Why are elementary row operations useful?

When Elementary Row Operations (EROs) are taught in an introductory setting (for instance, a one-semester multi-department undergrad course), they are often presented as steps in "mental algorithms" to find the inverse of a matrix, or to solve systems of equations. "How to use EROs" is often far more emphasized than "What EROs are". For those who share this experience, row operations remain mysterious and intriguing.

How does one understand what an Elementary Row Operation is? Can EROs be described in such a way that makes their usefulness more apparent?

• Elementary row operations are natural transformations. See page 60, Corollary 2.29 of math.jhu.edu/~eriehl/context.pdf for example. – Ishan Levy Feb 7 '18 at 6:46
• You've been reading the wrong introductory books. The answers to all your questions have been well-known for centuries (you could've got the history from Wikipedia's article on Gaussian elimination). You make it sound like you're the first person to ask Deep Questions about these things, or reveal their true importance; I'd recommend adjusting your tone. – symplectomorphic Feb 7 '18 at 7:36
• I adjusted the tone. Despite these being very old and well-investigated questions, perhaps even exhaustively covered in certain introductory textbooks, the fact remains that many are looking for illuminating but brief answers to these questions after an introductory course. – OrangeSherbet Feb 7 '18 at 18:37
• @OrangeSherbet Most people have exposure to row reduction prior to taking linear algebra as it is ubiquitous in application. This is likely why their justification is given so little attention in introductory courses as they are almost reflexive by the time a student encounters them there. – CyclotomicField Feb 7 '18 at 18:53
• Right @DWadet64, "preserving the original problem" is an important property of EROs. Then you have to explain what that means (the set of solutions is preserved?). But then the question is why these operations have this property (EROs are reversible / bijective?), and beyond that what other properties EROs have that set them apart from other reversible operations (they seem to be suited for matrix multiplication?). These are questions people likely either find obvious or unimportant, or confusing and intriguing. I'm in the latter crowd, but it seems everyone else is of the former. – OrangeSherbet Feb 17 '18 at 3:36

(If you have more insights please share them!)

Hope this helps someone.

I found understanding what a bijective function is helped with understanding what elementary row operations are, and why they are useful. This short piece argues that viewing Elementary Row Operations as a convenient but complete set of bijective functions for matrix multiplication is a useful and illuminating viewpoint. It shows one example of why viewing them in this way makes their utility in finding inverses more apparent.

## Bijective Functions

A bijective function: A bijective (or one-to-one) function is a function (it returns an output given some input) that is bijective; it returns an output that is unique for every input. Crucially, this means that the effect of the function can be undone, reversed, inverted; two inputs will never become the same output.

With any function (not just bijective ones), you can apply the function to both sides of an equality expression and preserve the equality. If you have any equality expression, for instance $$A \times B=C$$ Then you know that the equality is preserved applying any function to both sides. $$f(A \times B) = f(C)$$ However, only bijective functions can be inverted. If a function $$f$$ is truly bijective, you know that there exists another function $$f^{-1}$$ that can completely undo it. Only for a bijective function $$f$$, if

$$f(A \times B)=f(C)$$

then there exists an "inverse" function $$f^{-1}$$ that can always (for any input) undo $$f$$: $$f^{-1}( f(A \times B)) = A \times B = f^{-1}( f(C)) = C$$

One useful property for a bijective function is that you can correctly write the following:

$$f(D) = f(E) \space \space if \space and \space only \space if \space \space D = F$$

[A famous example of a not-bijective function is multiplying by zero. $$anything\times 0=0$$. Just because anything multiplied by zero is zero does not imply anything equals anything!]

## Invertible Matrices

In linear algebra, our tools are expressions like $$A \times B + C = D$$. These expressions are built from addition and multiplication only.

An extremely basic and useful function in linear algebra is a function that takes a matrix, and outputs the same matrix multiplied by another matrix. For instance $$f(A) = F \times A$$ Where $$A$$ and $$F$$ are both matrices, and $$f$$ is a function that performs matrix multiplication.

Let's consider whether or not multiplication by $$F$$ is bijective.

If multiplication by $$F$$ is bijective, in linear algebra we call $$F$$ an invertible matrix, since multiplication by $$F$$ can be "inverted".

There are many, many different invertible matrices. But all such matrices have something in common: they can all be made out of ("generated" by) three types of elementary matrices, which we call $$E_1$$, $$E_2$$, and $$E_3$$. Some multiplication sequence of just these three types can "generate" any invertible matrix $$F$$.

$$F = E_1 E_2 E_1 E_3 E_1 E_1...$$

Whatever these elementary matrices are, what we see above is a sequence of matrices that claims to be equivalent to a single invertible matrix. This requires that all the matrices above be invertible matrices (or in other words that multiplication by any one of them is bijective), such that the entire chain of matrix multiplications is invertible just like $$F$$.

The really neat part is, it turns out that multiplication by a single elementary matrix corresponds exactly to performing a single elementary row operation.

• $$E_1 \times A$$ corresponds to switching rows of $$A$$
• $$E_2 \times A$$ corresponds to multiplying a row of $$A$$
• $$E_3 \times A$$ corresponds to adding to a row of $$A$$

The three elementary row operations are convenient and simple; they correspond to easy-to-perform manipulations on paper. Yet, in combination, these three simple operations are able to accomplish anything any bijective matrix multiplication could; they can generate all the invertible matrices via multiplication.

The extremely well-known use-case is that of inverting the matrix function $$f(A) = F\times A$$, where $$F$$ is a matrix, and $$A$$ can be anything. No matter what $$F$$ is, if multiplying by $$F$$ can be undone, it can always be undone with an appropriate sequence of elementary row operations. If you can find a sequence of only row operations $$E$$'s such that you turn some matrix $$F$$ into the identity matrix

$$E_1 \space E_2 \space E_1 \space E_3 \space F = I$$

where $$I$$ is the identity matrix, you are guaranteed (by virtue of only using bijective operations) to have found the inverse of F, represented by a sequence of EROs:

$$F^{-1} = E_1 \space E_2 \space E_1 \space E_3$$

In practice, you don't have to remember what this sequence is. People just perform the same row operations on $$F$$ and $$I$$, the identity matrix, side-by-side, until $$F$$ becomes $$I$$, and $$I$$ becomes $$F^{-1}$$.

• This is a very convoluted explanation that does not at all explain the importance/justification of row operations for me. (which are actually quite obviously useful and well justified in any introductory text) – Morgan Rodgers Feb 7 '18 at 15:12

To explain the essence of elementary row operations in a nutshell, you are basically comparing linear equations with each other in order to find the value for each individual variable. You may have seen puzzles like these before:

2 Apples + 4 Bananas + 1 Pear = 11 Euros/Dollars

2 Apples + 2 Bananas + 1 Pear = 7 Euros/Dollars

1 Apple + 1 Banana + 0 Pears = 3 Euros/Dollars

You can rewrite this into a matrix like this:

$\begin{bmatrix}2 & 4 & 1 & | & 11\\2 & 2 & 1 & | & 7\\1 & 1 & 0 & | & 3\end{bmatrix}$

Using elementary row operations, you compare certain results to estimate individual values (prices of the different kinds of fruit).

In this case, you know from the 2nd row that 2 apples, 2 bananas and 1 pear cost 7 euros/dollars. If you reduce these values from the 1st row. You find that 0 apples, 2 bananas and 0 pears cost 4 euros/dollars. Divide all these values in this row by 2 and you find that 1 banana cost 2 euros/dollars. Using more of these elementary row operations allows you to find the values of all the different kinds of fruits.