Other Elementary Row Operations

linear algebramatricesmatrix decomposition

The three elementary row operations are:

Row switching
Row multiplication
Row addition

Each of these actions is a, in a sense, a 'do nothing' action on a linear system of equations. They can be applied without affecting the solution to the equation. It follows too, that if each of these actions 'does nothing', repeated application of them also doesn't affect the solution, so all compositions of elementary row operations also 'do nothing'. My question is, can all possible 'do nothing' actions be written as a composition of these elementary row operations?

Furthermore, my understanding is that row switching can be expressed using only Row multiplication (2) and Row addition (3). What would be the smallest list of 'atoms' (i.e. matrices which can't be composed from simpler matricies) to create all do nothing actions? Is Row addition sufficient to create all 'do nothing' matrices, and how could one show that no other 'do nothing' matrices exist?

Best Answer

Yes, all "do nothing" operations are compositions of elementary row operations. If two systems are equivalent, then you can use elementary row operations to bring the first system to reduced row-echelon form, and then use more elementary row operations on that reduced row-echelon form to get to the second system, since the inverse of an elementary row operation is also an elementary row operation.

Related Solutions

[Math] way to extract the diagonal from a matrix with simple matrix operations

Note: This solution is not working for the updated question. $$ D = \text{diag}(a_{11}, \ldots, a_{nn}) = \sum_{i=1}^n P_{(i)} A P_{(i)} $$ where $P_{(i)}$ is the projection on the $i$-th coordinate: $$ (P_{(i)})_{jk} = \delta_{ij} \delta_{jk} \quad (i,j,k \in \{1,\ldots,n\}) $$ and $\delta$ is the Kronecker delta ($1$ for same index values, otherwise $0$).

Transforming the diagonal matrix $D$ into a row vector can be done by $$ d = u^T D $$ where each of the $n$ components of $u$ is $1$. $$ u = (1,1,\ldots,1)^T $$ Combining both gives $$ d = \sum_i u^T P_{(i)} A P_{(i)} = \sum_i e_i^T A P_{(i)} $$ where $e_i$ is the $i$-th canonical base vector.

Example:

octave> A, P1, P2, u
A =
   1   2
   3   4

P1 =
   1   0
   0   0

P2 =
   0   0
   0   1

u =
   1
   1

octave> u'*(P1*A*P1+P2*A*P2)
ans =
   1   4

Is every invertible matrix a composition of elementary row operations

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.

Best Answer

Related Solutions

[Math] way to extract the diagonal from a matrix with simple matrix operations

Is every invertible matrix a composition of elementary row operations

Related Question