Row equivalence
Row equivalence is a fundamental concept in linear algebra that defines an equivalence relation between matrices of the same dimensions over a field, where two matrices are considered row equivalent if one can be transformed into the other through a finite sequence of elementary row operations.[1] These operations include swapping two rows, multiplying a row by a nonzero scalar from the field, and adding a scalar multiple of one row to another row.[2] Row equivalence preserves essential properties of the matrices, such as the solution set of the corresponding system of linear equations, the row space, the null space (kernel), and the rank.[1] A key application is Gaussian elimination, which uses these operations to reduce a matrix to its unique reduced row echelon form (RREF), facilitating the solution of linear systems, determination of matrix invertibility, and computation of bases for subspaces.[3] Every matrix is row equivalent to exactly one RREF, ensuring that the process yields consistent and canonical results regardless of the sequence of operations applied.[2] This equivalence relation underpins much of matrix theory and is crucial for understanding linear transformations and their invariants, such as the rank-nullity theorem, which relates the dimensions of the kernel and image.[4]Basic Concepts
Elementary row operations
Elementary row operations are the fundamental transformations applied to the rows of a matrix that facilitate the solution of linear systems and the analysis of matrix properties. These operations are reversible and form the basis for row reduction techniques in linear algebra. There are three types of elementary row operations: interchanging two rows, multiplying a row by a nonzero scalar, and adding a scalar multiple of one row to another row.[5][6][7] The first operation, interchanging two rows, denoted as R_i \leftrightarrow R_j for i \neq j, swaps the positions of row i and row j in the matrix. This operation is useful for reordering equations in a system to prioritize leading coefficients. The second operation multiplies a single row by a nonzero scalar k \in F, denoted R_i \to k R_i, which scales all entries in row i by k; this is commonly used to normalize leading entries to 1. The third operation adds a scalar multiple of one row to another, denoted R_j \to R_j + k R_i for i \neq j and k \in F, which modifies row j without altering row i; this allows elimination of entries below or above pivots in row reduction.[8][6][7] Each elementary row operation on an m \times n matrix A corresponds to left-multiplication by an m \times m elementary matrix E, resulting in EA, where E is obtained by applying the same operation to the m \times m identity matrix I_m. For row interchange R_i \leftrightarrow R_j, E is a permutation matrix with rows i and j swapped. For scaling R_i \to k R_i, E is a diagonal matrix identical to I_m except for the (i,i)-entry, which is k. For the addition R_j \to R_j + k R_i, E is I_m with an additional k in the (j,i)-entry, forming a shear matrix. These elementary matrices are invertible, with inverses obtained by reversing the operation (e.g., using -k for addition or $1/k for scaling).[8][9] A key motivation for these operations is that they preserve the solution set of the linear system Ax = b, where A is the coefficient matrix and b is the constant vector; applying an elementary row operation to the augmented matrix [A \mid b] yields an equivalent system with the same solutions. Row equivalence arises as the relation between matrices that can be transformed into one another via finite sequences of these operations.[5][7][9]Definition of row equivalence
In linear algebra, two m \times n matrices A and B over a field F (such as the real numbers \mathbb{R} or complex numbers \mathbb{C}) are said to be row equivalent, denoted A \sim B, if B can be obtained from A by applying a finite sequence of elementary row operations.[10][4] This relation is defined for matrices of compatible dimensions, meaning they must share the same number of rows and columns, with no further restrictions on m or n.[2] The row equivalence relation \sim is an equivalence relation on the set of all m \times n matrices over F.[10] To verify this, first note reflexivity: for any matrix A, A \sim A holds by applying the identity sequence of zero elementary row operations.[10] Symmetry follows from the invertibility of elementary row operations; if A \sim B via a sequence of elementary matrices E_1, \dots, E_k such that E_k \cdots E_1 A = B, then A = E_1^{-1} \cdots E_k^{-1} B, where each E_i^{-1} corresponds to an elementary row operation, so B \sim A.[10] Transitivity is established by composition: if A \sim B via E_1, \dots, E_k and B \sim C via F_1, \dots, F_l, then F_l \cdots F_1 E_k \cdots E_1 A = C, a sequence of elementary row operations, so A \sim C.[10] As an equivalence relation, row equivalence partitions the set of m \times n matrices over F into equivalence classes, where each class consists of all matrices row equivalent to a given matrix.[2][11]Illustrative examples
To illustrate row equivalence, consider a simple 2×2 example where two matrices are related through row interchange and scaling operations. Let matrix A = \begin{pmatrix} 1 & 2 \\ 4 & 5 \end{pmatrix} and matrix B = \begin{pmatrix} 4 & 5 \\ 1 & 2 \end{pmatrix}. These matrices are row equivalent because B can be obtained from A by interchanging the two rows, which is an elementary row operation.[5] Further, scaling the first row of B by \frac{1}{4} yields C = \begin{pmatrix} 1 & \frac{5}{4} \\ 1 & 2 \end{pmatrix}, and subtracting the first row from the second row gives D = \begin{pmatrix} 1 & \frac{5}{4} \\ 0 & \frac{3}{4} \end{pmatrix}. Thus, A \sim B \sim C \sim D, as each step preserves row equivalence.[5] For a 3×3 example demonstrating all three types of elementary row operations, start with matrix E = \begin{pmatrix} 1 & 3 & 2 \\ 3 & 1 & 5 \\ 0 & 0 & 3 \end{pmatrix}. First, interchange the first and second rows to get F = \begin{pmatrix} 3 & 1 & 5 \\ 1 & 3 & 2 \\ 0 & 0 & 3 \end{pmatrix}. Next, scale the first row of F by \frac{1}{3} to obtain G = \begin{pmatrix} 1 & \frac{1}{3} & \frac{5}{3} \\ 1 & 3 & 2 \\ 0 & 0 & 3 \end{pmatrix}. Then, subtract the first row from the second row to yield H = \begin{pmatrix} 1 & \frac{1}{3} & \frac{5}{3} \\ 0 & \frac{8}{3} & \frac{1}{3} \\ 0 & 0 & 3 \end{pmatrix}, which is in row echelon form. This sequence shows E \sim F \sim G \sim H, highlighting how row operations transform the matrix while maintaining equivalence.[12] A counterexample of non-equivalence occurs when two matrices have different row spaces. Consider I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} and J = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}. The row space of I is \mathbb{R}^2, spanned by the standard basis vectors, while the row space of J is the subspace spanned solely by (1, 0). Since their reduced row echelon forms are themselves and differ, I \not\sim J.[5] Row equivalence partitions the set of all m \times n matrices into equivalence classes, where two matrices belong to the same class if and only if they share the same reduced row echelon form. For instance, all invertible 2×2 matrices are equivalent to the 2×2 identity matrix, forming one such class, while singular matrices with rank 1 form another class equivalent to \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}. This partitioning underscores that row equivalence captures structural similarities preserved under elementary row operations.[7]Invariant Properties
Row space
The row space of an m \times n matrix A over the real numbers, denoted \Row(A), is the subspace of \mathbb{R}^n spanned by its row vectors \mathbf{r}_1, \mathbf{r}_2, \dots, \mathbf{r}_m. It consists of all possible linear combinations \sum_{i=1}^m c_i \mathbf{r}_i, where c_i \in \mathbb{R}.[13][14] This subspace remains invariant under elementary row operations, which include swapping two rows, multiplying a row by a nonzero scalar, or adding a scalar multiple of one row to another. Each such operation on A is equivalent to left-multiplication by an invertible elementary matrix E, yielding EA. The rows of EA are linear combinations of the rows of A, so \Row(EA) \subseteq \Row(A). Conversely, since E is invertible, multiplying by E^{-1} shows \Row(A) \subseteq \Row(EA), establishing equality. A sequence of such operations, corresponding to left-multiplication by a product of invertible matrices, thus preserves the row space.[15][14] The dimension of \Row(A) is defined as the rank of A, which equals the maximum number of linearly independent rows. A basis for \Row(A) can be extracted from the nonzero rows of the row echelon form obtained via row reduction, as these rows form a linearly independent spanning set for the space.[13][15] For example, consider the matrix A = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{pmatrix}. The row space is spanned by \mathbf{r}_1 = (1, 2, 3) and \mathbf{r}_2 = (2, 4, 6), but \mathbf{r}_2 = 2 \mathbf{r}_1, so a basis is \{ (1, 2, 3) \} with dimension 1. Performing the elementary operation of adding -2 times the first row to the second yields B = \begin{pmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \end{pmatrix}, whose row space is spanned by (1, 2, 3), identical to that of A.[15]Rank and null space
The rank of a matrix A, denoted \operatorname{rank}(A), is defined as the dimension of its row space, which equals the dimension of its column space.[16] This equality holds because the row space and column space of any matrix share the same dimension, a fundamental property arising from the structure of linear transformations represented by the matrix.[17] Row equivalence preserves the rank of a matrix because elementary row operations do not alter the linear dependence relations among the rows, thereby maintaining the dimension of the row space.[13] A sketch of the proof involves reducing the matrix to row echelon form via these operations; the rank equals the number of pivot positions in this form, and such operations leave the number of pivots unchanged, as swapping rows, scaling rows by nonzero scalars, or adding multiples of one row to another preserves the existence and positions of leading nonzero entries across columns.[18] The null space of a matrix A, denoted \operatorname{Null}(A), consists of all vectors x such that Ax = 0, and row equivalent matrices A and B share the same null space.[19] This invariance occurs because row operations correspond to left-multiplication by invertible elementary matrices, which transform the equation Ax = 0 to EAx = 0 where E is invertible, preserving the solution set since multiplying both sides by E^{-1} recovers the original equation.[4] By the rank-nullity theorem, the nullity of A (dimension of \operatorname{Null}(A)) satisfies \operatorname{nullity}(A) = n - \operatorname{rank}(A) for an m \times n matrix, so row equivalent matrices have the same nullity and thus the same solution space for the corresponding homogeneous systems Ax = 0.[20]Invertibility and transformations
A square matrix A of size n \times n is invertible if and only if it is row equivalent to the n \times n identity matrix I_n.[21][22] This criterion follows from the fact that performing elementary row operations on A to reach I_n corresponds to left-multiplying A by a sequence of elementary matrices, each of which is invertible, yielding I_n = E_k \cdots E_1 A, so A^{-1} = E_k \cdots E_1.[23] Conversely, if A is invertible, then A^{-1}A = I_n, and since the inverse can be obtained via row operations on the augmented matrix [A \mid I_n], A is row equivalent to I_n.[24] If two matrices A and B (both of size m \times n) are row equivalent, then there exists an invertible m \times m matrix P such that B = P A.[25][26] Here, P is the product of the elementary matrices corresponding to the sequence of row operations transforming A into B, ensuring P is invertible as each elementary matrix has an inverse.[27] For square matrices, this representation highlights that row equivalence preserves the invertibility of matrices within the same equivalence class. In the context of square matrices, all invertible matrices in a given row equivalence class are related by left-multiplication by invertible matrices, meaning if A and B are both invertible and row equivalent, then B = P A for some invertible P, and similarly A = P^{-1} B.[28] This property underscores that row equivalence classes partition the set of invertible square matrices into subsets where transformations via invertible left-multipliers connect class members. For such matrices, the equivalence also implies full rank n, reinforcing invertibility.[29] Row operations preserve the non-zero determinant of invertible matrices up to sign changes from row interchanges, ensuring that invertibility (non-zero determinant) is a class invariant under row equivalence.[30][31]Equivalent Characterizations
Via reduced row echelon form
The reduced row echelon form (RREF) of a matrix is a specific type of row echelon form that satisfies additional conditions: each leading entry (pivot) in a nonzero row is 1, and every entry above and below each pivot is zero.[3] This form serves as a canonical representative for the equivalence class of matrices under row equivalence, meaning that every matrix is row equivalent to exactly one matrix in RREF.[32] To obtain the RREF of a matrix, apply Gaussian elimination to transform it into row echelon form, followed by a backward elimination phase to normalize the pivots to 1 and clear the entries above them.[33] This process uses elementary row operations, ensuring the resulting form is unique regardless of the sequence of operations performed.[3] A fundamental theorem states that two matrices A and B are row equivalent if and only if they have the same reduced row echelon form.[32] This equivalence provides a computational criterion for determining whether matrices share the same row space and rank. The RREF of a matrix encodes key structural properties: the rank is the number of nonzero rows (or pivots), the positions of the leading 1's indicate the pivot columns, and the columns without pivots correspond to free variables in associated linear systems.[34] These features make RREF particularly useful for analyzing the solution space and dependencies within the matrix.[35]Via shared row space
An alternative characterization of row equivalence states that two m \times n matrices A and B over a field are row equivalent if and only if they share the same row space, that is, \operatorname{Row}(A) = \operatorname{Row}(B).[36][37] This equivalence arises because elementary row operations correspond to left multiplication by an invertible matrix P, yielding B = PA, which preserves the span of the rows since the image under an invertible transformation remains unchanged.[38] The shared row space implies that row equivalent matrices span identical subspaces of the ambient vector space, ensuring that the linear dependencies among their rows are preserved in structure. Specifically, the relations \sum c_i \mathbf{r}_i = \mathbf{0}, where \mathbf{r}_i are the rows, define the kernel of the associated linear map from the row index space to the column space, and this kernel's properties (such as dimension m - \operatorname{[rank](/page/Rank)}(A)) remain invariant under row equivalence.[38][39] Furthermore, this shared subspace allows for flexible basis constructions: any basis for \operatorname{Row}(A) can be extended to the full set of rows of a row equivalent matrix B, as the rows of B form a spanning set for the same space and can incorporate the basis vectors through appropriate linear combinations preserved by the invertible transformation relating A and B.[38] In contrast, elementary column operations preserve the column space of a matrix rather than the row space.[39]Proof of equivalence
To prove that two matrices are row equivalent if and only if they have the same row space, consider matrices over a field, where row equivalence is defined via sequences of elementary row operations (swapping two rows, multiplying a row by a nonzero scalar, or adding a scalar multiple of one row to another).[40] Forward direction: Suppose matrices A and B (both m \times n) are row equivalent, so B = PA for some invertible matrix P obtained as a product of elementary matrices. Each row of B is then a linear combination of the rows of A, implying that the row space of B is a subspace of the row space of A. Since P is invertible, A = P^{-1}B, so each row of A is a linear combination of the rows of B, and the row space of A is a subspace of the row space of B. Thus, the row spaces are equal. This holds because each elementary row operation corresponds to left-multiplication by an invertible matrix, preserving the span of the rows.[40][13] Backward direction: Suppose A and B have the same row space. Each matrix has a unique reduced row echelon form (RREF), obtained via elementary row operations, and the nonzero rows of the RREF form a basis for the row space. Since the row spaces of A and B coincide, their RREFs must have the same nonzero rows (up to the basis they span), and thus the same RREF (padding with zero rows if necessary to match dimensions). Therefore, A and B both reduce to the same RREF via elementary row operations, implying A and B are row equivalent. This avoids issues with zero rows, as the RREF uniquely encodes the row space basis over a field.[40][41]Applications
Solving linear systems
Row equivalence provides a systematic method for solving linear systems of the form Ax = b, where A is an m \times n coefficient matrix, x is the n \times 1 vector of variables, and b is the m \times 1 constant vector. The approach involves forming the augmented matrix [A \mid b] and applying elementary row operations—interchanging rows, scaling a row by a nonzero scalar, or adding a multiple of one row to another—to transform it into reduced row echelon form (RREF), denoted [R \mid c]. These operations ensure that the resulting system is equivalent to the original, preserving the solution set, because row equivalent augmented matrices represent systems with identical solutions.[42][43] In the RREF, pivot columns correspond to basic variables, while non-pivot columns indicate free variables. A particular solution x_p is obtained by setting free variables to zero and solving for the basic variables using the transformed constants in c. The general solution is then x = x_p + x_n, where x_n is any vector in the null space of A, whose basis can be derived from the RREF of A by assigning parameters to free variables and solving for basic variables (yielding special solutions). This method leverages the fact that row reduction to RREF uniquely identifies the solution structure while maintaining equivalence.[44] The existence and uniqueness of solutions are classified using ranks, which remain invariant under row operations: if \operatorname{rank}(A) = \operatorname{rank}([A \mid b]) = n, the system has a unique solution; if \operatorname{rank}(A) = \operatorname{rank}([A \mid b]) < n, there are infinitely many solutions parameterized by the null space dimension; if \operatorname{rank}(A) < \operatorname{rank}([A \mid b]), the system is inconsistent with no solution. This classification briefly references the rank as the dimension of the row space and the null space dimension as n - \operatorname{rank}(A), determining the number of free variables.[45] Consider the following 3×3 system as an illustrative example of the process leading to a unique solution: \begin{cases} x - y + z = 8 \\ 2x + 3y - z = -2 \\ 3x - 2y - 9z = 9 \end{cases} The augmented matrix is [A \mid b] = \begin{bmatrix} 1 & -1 & 1 & \mid & 8 \\ 2 & 3 & -1 & \mid & -2 \\ 3 & -2 & -9 & \mid & 9 \end{bmatrix}. Apply row operations to reach RREF:- R_2 \leftarrow R_2 - 2R_1:
- R_3 \leftarrow R_3 - 3R_1:
- Swap R_2 and R_3:
- R_3 \leftarrow R_3 - 5R_2:
- R_3 \leftarrow \frac{1}{57} R_3:
- R_2 \leftarrow R_2 + 12 R_3:
- R_1 \leftarrow R_1 + R_2 - R_3: