Is every invertible matrix a composition of elementary row operations?

Question

If $A$ is invertible that means we can multiply it on the left by matrices $E_1, ..., E_k$ that correspond to elementary row operations until we get the identity matrix $I$. In other words, we get $E_1 \cdots E_k A = I$. Hence the inverse of $A$ is $E_1 \cdots E_k$, which is a composition of elementary row operations. Since the inverse of a composition of elementary row operations is also a composition of elementary row operations, $A$ is also a composition of elementary row operations.

I'm just wondering if this means that the set of all compositions of elementary row operations is the same as the set of all invertible matrices. I just find this interesting and somewhat surprising because I've never heard about it described this way. Am I thinking about it correctly or is there a flaw in my reasoning?

Answer 1

Given an $n$-dimensional vector space $V$ and an ordered basis $\mathscr B$ of $V,$ it is true that one can identify a linear operator $T : V \to V$ with an $n \times n$ matrix $A.$ Explicitly, we can compute $T(v_i)$ for each of the vectors $v_i \in \mathscr B,$ and we can subsequently form the matrix $A$ whose $i$th column is $v_i.$

Like you mentioned, if $A$ is an invertible $n \times n$ matrix, then one can compute the inverse of $A$ by a sequence of elementary row operations $E_1, \dots, E_k.$ Each elementary row operation is a linear operator $E_i : V \to V.$ Composition of linear operators corresponds to multiplication of the matrices that represent the linear operators, so as you said, we find that $E_k \cdots E_1 A = I.$ (Here, I am slightly abusing notation and using $E_i$ for both the linear operator and the matrix that represents it with respect to the ordered basis $\mathscr B.$) From this, you can see (as you have) that an invertible $n \times n$ matrix gives rise to a composition of elementary row operations.

Conversely, we may start with a composition $E_k \circ \cdots \circ E_1$ of elementary row operations $E_i : V \to V.$ Observe that for each elementary row operation $E_i,$ there exists an elementary row operation $F_i$ such that $F_i \circ E_i = I,$ from which it follows that $(F_1 \circ \cdots \circ F_k) \circ (E_k \circ \cdots \circ E_1) = I.$ (Basically, $F_i$ is the linear operator that does the "opposite" of what $E_i$ does. For instance, if $E_i$ sends $R_1$ to $3R_1 - R_2,$ then $F_i$ sends $R_1$ to $\frac{1}{3}(R_1 + R_2),$ and we have that $F_i \circ E_i = I = E_i \circ F_i$).

Consequently, we have that $T = E_k \circ \cdots \circ E_1$ is an invertible linear operator, hence there exists an invertible $n \times n$ matrix that corresponds to $T.$ (Use the construction from the first paragraph above.) From this, you can see (as you have) that a composition of elementary row operations gives rise to an invertible $n \times n$ matrix.