Elementary Operations
Elementary Matrices
The following three types of square matrices are called elementary matrices.
Scaling Matrix
A scaling matrix is a special kind of diagonal matrix.
It represents a diagonal matrix where the \(i\)-th element on the main diagonal is \(k\), with the stipulation that \(k\) cannot be \(0\), and all other elements are \(1\).
In particular, when \(k\) is \(1\), \(D_i(1)\) is the identity matrix \(I\).
Permutation Matrix
A permutation matrix is a special kind of symmetric matrix.
The elements of a permutation matrix are all \(1\)s and \(0\)s. All other elements on the main diagonal are \(1\), except the \(i\)-th and \(j\)-th elements which are \(0\). The elements at the \(i\)-th row, \(j\)-th column and the \(j\)-th row, \(i\)-th column are \(1\).
A permutation matrix requires \(i\) and \(j\) to be distinct.
Row Addition Matrix
A row addition matrix is obtained from the identity matrix \(I\) by setting the element at the \(i\)-th row and \(j\)-th column to \(k\).
A row addition matrix requires \(i\) and \(j\) to be distinct. If \(k\) is \(0\), then \(T_{ij}(0)\) degenerates to the identity matrix \(I\).
A row addition matrix is either an upper triangular matrix or a lower triangular matrix.
Determinants of Elementary Matrices
The three types of elementary matrices have the following determinants:
Since the determinant of a product of square matrices equals the product of their determinants, and given the equivalence between elementary transformations and matrix multiplication discussed later, this property of elementary matrices can be used in determinant calculation.
Elementary Transformations
Not limited to square matrices, for a general matrix \(A\), one can perform elementary row transformations and elementary column transformations, collectively called elementary transformations.
Elementary row transformations and elementary column transformations both have three types: multiplication, switching, and addition. Here we first introduce elementary row transformations:
- Multiply row \(i\) by a non-zero scalar \(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\).
Changing "row" to "column" in the above operations yields elementary column transformations.
In elementary transformations, switching can be achieved through multiplication and addition. Clearly, addition cannot be achieved through multiplication and switching. With knowledge of determinants and the equivalence between elementary transformations and matrix multiplication discussed later, it can also be shown that multiplication cannot be achieved through addition and switching.
Therefore, compared to switching, multiplication and addition are more fundamental operations. The switching operation is an auxiliary operation introduced to ensure orderly elimination in Gaussian elimination.
Elementary Transformations and Matrix Multiplication
It can be observed that the three types of elementary matrices are obtained by performing a corresponding transformation on the identity matrix \(I\). As pointed out later in the context of linear transformations, there is a correspondence between linear transformations and matrices, similar to the relationship here.
Regardless of whether matrix \(A\) is square, performing an elementary row transformation on \(A\) is equivalent to left-multiplying \(A\) by an elementary matrix. Performing an elementary column transformation on \(A\) is equivalent to right-multiplying \(A\) by an elementary matrix.
Multiplication Operation
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 a diagonal matrix. For multiplication of diagonal matrices, multiply the corresponding elements on the main diagonal. Since the identity matrix is a special scaling matrix, and scaling matrices require \(k \neq 0\), it can be seen that any diagonal matrix whose main diagonal elements are all non-zero can be decomposed into a product of scaling matrices.
For general diagonal matrices, regardless of whether elements are zero, similar conclusions hold. Left-multiplying by a diagonal matrix is equivalent to multiplying the corresponding rows by certain factors, exactly the corresponding elements on the main diagonal of the diagonal matrix. Right-multiplying by a diagonal matrix performs the same operation on the corresponding columns.
Since the determinant of scaling matrix \(D_i(k)\) is \(k\), after performing a multiplication operation on a row or column of a square matrix, the determinant of the square matrix becomes \(k\) times the original. The determinant of a diagonal matrix is the product of its main diagonal elements.
Multiplication of scaling matrices is commutative, and multiplication of diagonal matrices is also commutative. When multiplying only diagonal matrices, the order can be arbitrarily arranged.
The multiplication operation corresponding to the identity matrix leaves matrix \(A\) unchanged and is not performed in practical applications.
Switching Operation
Left-multiplying by a permutation matrix \(P_{ij}\) is equivalent to swapping row \(i\) and row \(j\). Right-multiplying by a permutation matrix \(P_{ij}\) is equivalent to swapping column \(i\) and column \(j\).
Similar to the relationship between scaling matrices and diagonal matrices, the concept of a permutation matrix is introduced here. A permutation matrix is a square matrix with exactly one \(1\) in each row and each column, and all other entries are \(0\). The identity matrix \(I\) is also a special permutation matrix.
A permutation matrix corresponds to permuting the rows of the identity matrix \(I\), and also to permuting the columns of \(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. Right-multiplying by a permutation matrix is equivalent to permuting the columns of the original matrix. The permutation method is consistent with permuting the rows or columns of the identity matrix \(I\).
Permutation matrices correspond one-to-one with permutations. The multiplicative group formed by permutation matrices is isomorphic to the permutation group. Since, considering the identity transformation as a product of zero transpositions, any permutation can be decomposed into a product of transpositions, any permutation matrix can also be decomposed into a product of transposition matrices.
Since the determinant of a transposition matrix is \(-1\), after performing a switching operation on a row or column of a square matrix, the determinant of the square matrix becomes \(-1\) times the original.
Multiplication of transposition matrices is not commutative, and multiplication of permutation matrices is also not commutative.
The determinant of a permutation matrix is \({(-1)}^p\), where \(p\) is the number of inversions of the permutation corresponding to the permutation matrix, i.e., the number of transpositions in its decomposition.
Addition Operation
Left-multiplying by a row addition matrix \(T_{ij}(k)\) is equivalent to adding \(k\) times row \(j\) to row \(i\). Right-multiplying by a row addition matrix \(T_{ij}(k)\) is equivalent to adding \(k\) times column \(i\) to column \(j\).
If it's hard to remember, observe what operation the row addition matrix \(T_{ij}(k)\) performs on the identity matrix \(I\); they correspond. Left multiplication corresponds to row operations, right multiplication corresponds to column operations, following the mnemonic "left rows, right columns".
Since the determinant of a row addition matrix is \(1\), after performing an addition operation on a square matrix, the determinant of the square matrix remains unchanged.
Multiplication of row addition matrices is not commutative.
The addition operation corresponding to the identity matrix leaves matrix \(A\) unchanged and is not performed in practical applications.
Upper Triangular Matrix
A row addition matrix is either an upper triangular matrix or a lower triangular matrix. Since these two types are symmetric about the main diagonal, we discuss upper triangular matrices here. In fact, in this example, only elementary row transformations are needed, not column transformations.
If an upper triangular matrix has all \(1\)s on its main diagonal, it can be decomposed into a product of a sequence of row addition matrices. The decomposition order is: first perform addition operations on the first row of the identity matrix \(I\), then on the second row, and so on, until every row has been operated on.
Since multiplication of row addition matrices is not commutative, the order of these operations cannot be changed.
If an upper triangular matrix has all non-zero elements on its main diagonal, it can be decomposed into a product of a sequence of row addition matrices and scaling matrices. When operating on each row of the identity matrix \(I\), first perform a multiplication operation on that row, effectively setting the main diagonal element to the specified non-zero value.
If an upper triangular matrix has a \(0\) on its main diagonal, it cannot be decomposed into a product of a sequence of elementary matrices.
Regardless of whether the main diagonal of an upper triangular matrix contains zeros, its determinant equals the product of its main diagonal elements, consistent with diagonal matrices.
Transforming a Square Matrix into a Diagonal Matrix Using Addition Operations
Using only addition operations, any square matrix can be transformed into a diagonal matrix. This example requires both elementary row and column transformations.
If the first row and first column of the square matrix contain non-zero elements, addition operations can be used to make the top-left element non-zero. Then, using elementary row and column transformations, all elements in the first row and first column except the top-left element can be made \(0\).
If the first row and first column are already all \(0\), proceed directly to the second row and second column.
Using this method, one can even arrange that the non-zero elements of the diagonal matrix are all in the top-left corner.
If the first row and first column are already all \(0\), check the remaining rows and columns for non-zero elements. If there is any non-zero element, addition operations can be used to make some element in the first row or first column non-zero, reducing to the initial case and making the top-left element non-zero.
Only when the remaining rows and columns also have no non-zero elements can the top-left element not be made non-zero; at this point, the remaining submatrix is the zero matrix.
Row-Reduced Echelon Form
Using elementary transformations, any matrix, regardless of shape, can be reduced to its row-reduced echelon form.
The row-reduced echelon form has an identity matrix \(I\) as a submatrix in the top-left corner, with all other parts being \(0\). The reduction method is similar to transforming a square matrix into a diagonal matrix, and requires using multiplication operations to turn the top-left non-zero element into \(1\).
After transforming a matrix into row-reduced echelon form, the number of \(1\)s equals the rank of the matrix.
Invertible Matrices
Let \(A\) be an \(n \times n\) matrix. If there exists an \(n \times n\) matrix \(B\) such that \(AB = BA = I\), then \(A\) is called an invertible matrix or non-singular matrix, \(B\) is called the inverse of \(A\), and is denoted \(A^{-1}\).
If matrix \(A\) is invertible, then the inverse 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 inverse of the transpose equals the transpose of the inverse.
Inverses of Elementary Matrices
Elementary matrices are all invertible, and their inverses are elementary matrices of the same type:
Clearly, the identity matrix \(I\) is invertible, and its inverse is still \(I\).
Elementary transformations preserve the invertibility of matrices; before and after transformation, 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, i.e., can be transformed into the identity matrix \(I\) via elementary transformations.
After introducing determinants, we will know:
Matrix \(A\) is invertible if and only if the rank of \(A\) is \(n\), if and only if the determinant of \(A\) is non-zero.
A simple notation: let \(E_{ij}\) be the \(n\times n\) matrix with \(1\) at the \(i\)-th row, \(j\)-th column and \(0\) elsewhere. 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 inverse matrices.
Applications
Solving Linear Systems
For a system of linear equations, the coefficients before the unknowns form the coefficient matrix. Appending the constant terms of the equations to the right of the coefficient matrix forms the augmented matrix.
Applying elementary row transformations, the augmented matrix corresponding to the linear system can first be transformed into row echelon form, then into reduced row echelon form, thereby solving the linear system. This method is called Gaussian elimination for solving linear systems. The Gauss–Jordan elimination discussed later is an elimination algorithm performed in a specific order.
Determinant Calculation
Since the determinant of a product of square matrices equals the product of their determinants, the determinants of elementary matrices are easy to compute, and elementary transformations are equivalent to multiplication by elementary matrices, elementary transformations are also used in determinant calculation.
Since performing elementary transformations in a specific order is more convenient for programming, determinant calculation can also use the Gauss–Jordan elimination algorithm discussed later.
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用