Elementary transformations

Elementary matrices

The following three types of square matrices are called elementary matrices.

Scaling matrices

A scaling matrix is a special diagonal matrix.

$$D_i(k)=\operatorname{diag}\{1,\cdots,1,k,1,\cdots,1\}$$

It represents a diagonal matrix whose $i$-th diagonal entry is $k$, where $k$ is required not to be $0$, and all other entries are $1$.

In particular, when $k$ is $1$, $D_i(1)$ is the identity matrix $I$.

Switching matrices

A switching matrix is a special symmetric matrix.

$$P_{ij}=\begin{pmatrix} I_{i-1} & & & & \\ & 0 & & 1 & \\ & & I_{j-i-1} & & \\ & 1 & & 0 & \\ & & & & I_{n-j}\\ \end{pmatrix}$$

The entries of a switching matrix are all $1$ or $0$. All other diagonal entries are $1$; only the $i$-th and $j$-th diagonal entries are $0$, while the entries in row $i$, column $j$, and row $j$, column $i$, are $1$.

A switching matrix requires $i$ and $j$ to be distinct.

Addition matrices

An addition matrix is obtained from the identity matrix $I$ by setting the entry in row $i$, column $j$, to $k$.

$$T_{ij}(k)=\begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 1 & \cdots & k & & \\ & & & \ddots & \vdots & & \\ & & & & 1 & & \\ & & & & & \ddots & \\ & & & & & & 1\\ \end{pmatrix}$$

An addition matrix requires $i$ and $j$ to be distinct. If $k$ is $0$, then $T_{ij}(0)$ degenerates to the identity matrix $I$.

An addition matrix is either an upper-triangular or a lower-triangular matrix.

Determinants of elementary matrices

The three types of elementary matrices have determinants:

$$|D_i(k)|=k$$ $$|P_{ij}|=-1$$ $$|T_{ij}(k)|=1$$

Since the determinant of a product of square matrices equals the product of their determinants, together with the equivalence between elementary transformations and matrix multiplication described below, this property of elementary matrices can be used to calculate determinants.

Elementary transformations

Elementary row and column transformations can be performed not only on square matrices but also on a general matrix $A$; together, they are called elementary transformations.

There are three types of elementary row transformations and, similarly, elementary column transformations: scaling (multiplication), switching, and addition. We introduce elementary row transformations first:

• Multiply row $i$ by the nonzero number $k$: $B\mapsto D_i(k)B$.
• Swap rows $i$ and $j$: $B\mapsto P_{ij}B$.
• Add $k$ times row $j$ to row $i$: $B\mapsto T_{ij}(k)B$.

Replacing rows in the operations above with columns gives elementary column transformations.

Among elementary transformations, switching can be implemented using scaling and addition. Clearly, addition cannot be implemented using scaling and switching. Using determinants, together with the equivalence between elementary transformations and matrix multiplication described below, one can also show that scaling cannot be implemented using addition and switching.

Therefore, compared with switching, scaling and addition are more fundamental operations. Switching is an auxiliary operation introduced to keep elimination ordered during the elimination method.

Elementary transformations and matrix multiplication

The three types of elementary matrices can be seen as the results of applying the corresponding transformation once to the identity matrix $I$. The correspondence between linear transformations and matrices, described later, is analogous to the relationship here.

Regardless of whether matrix $A$ is square, applying an elementary row transformation to $A$ is equivalent to left-multiplying $A$ by an elementary matrix. Applying an elementary column transformation to $A$ is equivalent to right-multiplying $A$ by an elementary matrix.

Scaling operations

Left-multiplying by a scaling matrix $D_i(k)$ is equivalent to multiplying row $i$ by $k$. Right-multiplying by a scaling matrix $D_i(k)$ is equivalent to multiplying column $i$ by $k$.

The product of diagonal matrices is still diagonal; for diagonal-matrix multiplication, multiply the corresponding diagonal entries. Since the identity matrix is a special scaling matrix, while a scaling matrix requires $k$ not to be $0$, any diagonal matrix whose diagonal entries are all not $0$ can be decomposed into a product of scaling matrices.

For a general diagonal matrix, there is a corresponding conclusion regardless of whether its entries are $0$. Left-multiplying by a diagonal matrix is equivalent to multiplying each corresponding row by a factor equal to the corresponding diagonal entry. Right-multiplication by a diagonal matrix performs the same operation on the corresponding columns.

Since the determinant of the scaling matrix $D_i(k)$ is $k$, after scaling a row or column of a square matrix, its determinant becomes $k$ times the original determinant. The determinant of a diagonal matrix is the product of its diagonal entries.

Multiplication of scaling matrices is commutative, as is multiplication of diagonal matrices; when only diagonal matrices are involved in a product, their order may be arbitrary.

The scaling operation corresponding to the identity matrix leaves matrix $A$ unchanged, so this operation is not performed in practice.

Switching operations

Left-multiplying by a switching matrix $P_{ij}$ is equivalent to swapping rows $i$ and $j$. Right-multiplying by a switching matrix $P_{ij}$ is equivalent to swapping columns $i$ and $j$.

Analogously to scaling matrices and diagonal matrices, we introduce the concept of a permutation matrix. A permutation matrix is a square matrix with exactly one $1$ in every row and every column, and $0$ everywhere else. The identity matrix $I$ is also a special permutation matrix.

A permutation matrix is the same as permuting the rows of the identity matrix $I$, and also the same as permuting the columns of the identity matrix $I$. The identity matrix $I$ itself corresponds to the identity transformation.

Left-multiplying by a permutation matrix is equivalent to permuting the rows of the original matrix, while right-multiplying by a permutation matrix is equivalent to permuting its columns. The corresponding permutation is performed in the same way as permuting the rows or columns of the identity matrix $I$.

Permutation matrices correspond exactly to permutations, and the multiplicative group of permutation matrices is isomorphic to the permutation group. By the theorem that any permutation can be decomposed into a product of switches when the identity transformation is regarded as a product of zero switches, every permutation matrix can likewise be decomposed into a product of switching matrices.

Since the determinant of a switching matrix is $-1$, after switching rows or columns of a square matrix, its determinant becomes $-1$ times the original determinant.

Multiplication of switching matrices is not commutative, and neither is multiplication of permutation matrices.

The determinant of a permutation matrix is ${(-1)}^p$, where $p$ is the inversion count of the permutation corresponding to the permutation matrix, that is, the number of switches in its decomposition as a product of switches.

Addition operations

Left-multiplying by an addition matrix $T_{ij}(k)$ is equivalent to adding $k$ times row $j$ to row $i$. Right-multiplying by an addition matrix $T_{ij}(k)$ is equivalent to adding $k$ times column $i$ to column $j$.

If this is difficult to remember, observe what operation the addition matrix $T_{ij}(k)$ performs on the identity matrix $I$; the two correspond. Left multiplication operates on rows, and right multiplication operates on columns, following the mnemonic “left row, right column.”

Since the determinant of an addition matrix is $1$, addition operations on a square matrix leave its determinant unchanged.

Multiplication of addition matrices is not commutative.

The addition operation corresponding to the identity matrix leaves matrix $A$ unchanged, so this operation is not performed in practice.

Upper-triangular matrices

An addition matrix is either upper-triangular or lower-triangular. Since the two types of matrices are symmetric about the main diagonal, we discuss upper-triangular matrices here. In fact, this example only requires elementary row transformations, not column transformations.

If all diagonal entries of an upper-triangular matrix are $1$, it can be decomposed into a product of a sequence of addition matrices. The order is to first perform addition operations on the first row of the identity matrix $I$, then on the second row of $I$, and so on, until every row has been processed.

Because multiplication of addition matrices is not commutative, the order of the operations above cannot be changed.

If all diagonal entries of an upper-triangular matrix are not equal to $0$, it can be decomposed into a product of a sequence of addition and scaling matrices. When operating on each row of the identity matrix $I$, we can first scale that row, making its diagonal entry the specified nonzero value.

If an upper-triangular matrix has $0$ on its diagonal, it cannot be decomposed into a product of a sequence of elementary matrices.

Whether or not an upper-triangular matrix has $0$ on its diagonal, its determinant equals the product of its diagonal entries, just as for a diagonal matrix.

Converting a square matrix to a diagonal matrix using addition operations

Any square matrix can be converted to a diagonal matrix using only addition operations; this example requires both elementary row and elementary column transformations.

If the first row and first column of a square matrix contain nonzero entries, addition operations can make the upper-left entry nonzero. Elementary row and column transformations can then make every other entry in the first row and first column equal to $0$.

If the first row and first column of a square matrix are already all $0$, we can simply examine the second row and second column.

Using this method, we can even require all nonzero entries of the diagonal matrix to lie in the upper-left corner.

If the first row and first column of a square matrix are already all $0$, examine whether the remaining rows and columns contain any nonzero entries. If they do, addition operations can make some entry in the first row or first column not equal to $0$, reducing the situation to the initial case and making the upper-left entry not equal to $0$.

Only when the remaining rows and columns also contain no nonzero entries is it impossible to make the upper-left entry nonzero; at that point, the remaining square matrix is already the zero matrix.

Canonical-form matrices

Using elementary transformations, any matrix, regardless of its shape, can be reduced to a canonical-form matrix.

A canonical-form matrix has an identity matrix $I$ as a submatrix in its upper-left corner, with $0$ everywhere else. The reduction method is similar to converting a square matrix to a diagonal matrix, and also uses scaling operations to turn each nonzero upper-left entry into $1$.

After a matrix is converted to canonical form, the number of entries equal to $1$ is exactly the rank of the matrix.

Invertible matrices

Let $A$ be an $n$-th order matrix. If there exists an $n$-th order matrix $B$ such that $AB=BA=I$, then $A$ is called an invertible or nonsingular matrix, and $B$ is called the inverse matrix of $A$, denoted by $A^{-1}$.

If matrix $A$ is invertible, the inverse matrix of $A$ is uniquely determined by $A$.

The inverse $A^{-1}$ of an invertible matrix $A$ is also invertible, and the inverse of $A^{-1}$ is $A$.

The product $AB$ of two invertible matrices $A$ and $B$ is also invertible, with inverse $B^{-1}A^{-1}$.

The transpose $A^T$ of an invertible matrix $A$ is also invertible, and the transpose of the inverse equals the inverse of the transpose.

Inverses of elementary matrices

Every elementary matrix is invertible, and its inverse is an elementary matrix of the same type:

$${D_i(k)}^{-1}=D_i\left(\frac{1}{k}\right)$$ $$P_{ij}^{-1}=P_{ij}$$ $$T_{ij}(k)^{-1}=T_{ij}(-k)$$

Clearly, the identity matrix $I$ is invertible, and its inverse is still $I$.

Elementary transformations preserve invertibility: before and after a transformation, the matrices are either both invertible or both non-invertible.

Matrix $A$ is invertible if and only if $A$ can be written as a product of elementary matrices, equivalently, if and only if it can be transformed into the identity matrix $I$ by elementary transformations.

After determinants are introduced, we will know that:

Matrix $A$ is invertible if and only if matrix $A$ has rank $n$, if and only if matrix $A$ has determinant not equal to $0$.

A simple notation is to let $E_{ij}$ be the $n\times n$ matrix whose entry in row $i$, column $j$, is $1$ and whose other entries are zero. Then

• $D_i(k)=I_n+(k-1)E_{ii}$
• $P_{ij}=I_n-E_{ii}-E_{jj}+E_{ij}+E_{ji}$
• $T_{ij}(k)=I_n+kE_{ij}$

This notation can also be applied to their inverses.

Applications

Solving systems of linear equations

For a system of linear equations, the coefficients before the unknowns form the coefficient matrix. Appending the constant terms of the system to the right of the coefficient matrix forms the augmented matrix.

Using elementary row transformations, the augmented matrix corresponding to a system of linear equations can first be converted into row echelon form and then into reduced row echelon form, completing the solution of the system. This method is called solving a system of linear equations by elimination; the Gauss–Jordan elimination described later is an elimination algorithm that follows a prescribed order.

Determinant calculation

Since the determinant of a product of square matrices equals the product of their determinants, the determinants of elementary matrices are convenient to calculate, and since elementary transformations are equivalent to multiplication by elementary matrices, elementary transformations are also used when calculating determinants.

Because performing elementary transformations in a prescribed order is more convenient for writing programs, determinant calculation can also use the Gauss–Jordan elimination algorithm described later.