Matrix operations¶
Vectors and matrices · Chapter 4.2 · Lecture notes (PDF) · Exercises: Matrix operations · Slides (PDF) · App: Gaussian elimination · App: Determinant · App: Why partial pivoting
1. Elementary row and column operations¶
- Elementary row and column operations are fundamental tools in linear algebra. They are used in many algorithms, including Gaussian elimination, computation of the inverse matrix, and matrix factorizations (such as the LU decomposition)
Given a matrix \(\boldsymbol A \in \R^{m \times n}\), the elementary row operations are:
-
Row swap: Exchange rows \(i\) and \(k\).
\[ R_i \leftrightarrow R_k \] -
Row scaling: Multiply row \(i\) by a nonzero scalar \(\lambda \neq 0\).
\[ R_i \leftarrow \lambda R_i \] -
Row addition: Replace row \(i\) by the sum of row \(i\) and \(\lambda\) times row \(k\) (with \(i \neq k\)).
\[ R_i \leftarrow R_i + \lambda R_k \]
Example 1: Row swap
Consider the matrix
After swapping rows 1 and 3, i.e., \(R_1 \leftrightarrow R_3\), we obtain:
Example 2: Row scaling
Consider the matrix
After multiplying row 2 by \(\lambda = -2\), i.e., \(R_2 \leftarrow -2R_2\), we obtain:
Example 3: Row addition
Consider the matrix
After replacing row 2 with row 2 minus 4 times row 1, i.e., \(R_2 \leftarrow R_2 - 4R_1\), we obtain:
Indeed:
Given a matrix \(\boldsymbol A \in \R^{m \times n}\), the elementary column operations are:
-
Column swap: Exchange columns \(j\) and \(k\).
\[ C_j \leftrightarrow C_k \] -
Column scaling: Multiply column \(j\) by a nonzero scalar \(\lambda \neq 0\).
\[ C_j \leftarrow \lambda C_j \] -
Column addition: Replace column \(j\) by the sum of column \(j\) and \(\lambda\) times column \(k\) (with \(j \neq k\)).
\[ C_j \leftarrow C_j + \lambda C_k \]
Example 4: Column swap
Consider the matrix
After swapping columns 1 and 3, i.e., \(C_1 \leftrightarrow C_3\), we obtain:
Example 5: Column scaling
Consider the matrix
After multiplying column 2 by \(\lambda = 3\), i.e., \(C_2 \leftarrow 3C_2\), we obtain:
Example 6: Column addition
Consider the matrix
After replacing column 3 with column 3 plus 2 times column 1, i.e., \(C_3 \leftarrow C_3 + 2C_1\), we obtain:
Indeed:
2. Effect of elementary operations on the determinant¶
Let \(\boldsymbol A \in \R^{n \times n}\) be a square matrix. The elementary row operations affect the determinant as follows:
-
Row swap: \(R_i \leftrightarrow R_k\) changes the sign of the determinant.
\[ \det(\text{new matrix}) = -\det(\boldsymbol A) \] -
Row scaling: \(R_i \leftarrow \lambda R_i\) (with \(\lambda \neq 0\)) multiplies the determinant by \(\lambda\).
\[ \det(\text{new matrix}) = \lambda \det(\boldsymbol A) \] -
Row addition: \(R_i \leftarrow R_i + \lambda R_k\) (with \(i \neq k\)) does not change the determinant.
\[ \det(\text{new matrix}) = \det(\boldsymbol A) \]
Example 7: Effect of row swap on determinant
Consider the matrix
The determinant is:
After swapping rows 1 and 2, i.e., \(R_1 \leftrightarrow R_2\), we obtain:
The determinant of the new matrix is:
Example 8: Effect of row scaling on determinant
Consider the matrix
The determinant is:
After multiplying row 1 by \(\lambda = 2\), i.e., \(R_1 \leftarrow 2R_1\), we obtain:
The determinant of the new matrix is:
Example 9: Effect of row addition on determinant
Consider the matrix
The determinant is:
After replacing row 2 with row 2 minus 3 times row 1, i.e., \(R_2 \leftarrow R_2 - 3R_1\), we obtain:
The determinant of the new matrix is:
Let \(\boldsymbol A \in \R^{n \times n}\) be a square matrix. The elementary column operations affect the determinant as follows:
-
Column swap: \(C_j \leftrightarrow C_k\) changes the sign of the determinant.
\[ \det(\text{new matrix}) = -\det(\boldsymbol A) \] -
Column scaling: \(C_j \leftarrow \lambda C_j\) (with \(\lambda \neq 0\)) multiplies the determinant by \(\lambda\).
\[ \det(\text{new matrix}) = \lambda \det(\boldsymbol A) \] -
Column addition: \(C_j \leftarrow C_j + \lambda C_k\) (with \(j \neq k\)) does not change the determinant.
\[ \det(\text{new matrix}) = \det(\boldsymbol A) \]
Example 10: Effect of column swap on determinant
Consider the matrix
The determinant is:
After swapping columns 1 and 2, i.e., \(C_1 \leftrightarrow C_2\), we obtain:
The determinant of the new matrix is:
Example 11: Effect of column scaling on determinant
Consider the matrix
The determinant is:
After multiplying column 2 by \(\lambda = 3\), i.e., \(C_2 \leftarrow 3C_2\), we obtain:
The determinant of the new matrix is:
Example 12: Effect of column addition on determinant
Consider the matrix
The determinant is:
After replacing column 2 with column 2 plus 2 times column 1, i.e., \(C_2 \leftarrow C_2 + 2C_1\), we obtain:
The determinant of the new matrix is:
-
These properties follow from the fact that the determinant of a matrix is equal to the determinant of its transpose (see the properties of determinants in the chapter on matrices), and a column operation on a matrix is the corresponding row operation on its transpose. Hence column operations have the same effect on the determinant as the corresponding row operations.
-
These results are fundamental for understanding how determinants behave under elementary operations, which is crucial in algorithms such as Gaussian elimination and matrix factorization.
3. Gaussian elimination and row echelon form¶
- Elementary row operations can be used to transform any matrix into a matrix with a “staircase” structure, from which many properties of the original matrix (for example, its determinant) can be read easily. The systematic procedure that does this is called Gaussian elimination.
Definition 1: Row echelon form
A matrix \(\boldsymbol U \in \R^{m \times n}\) is in row echelon form if:
-
all its zero rows (if any) are below all its nonzero rows;
-
the first nonzero entry of each nonzero row (called the pivot of the row) is strictly to the right of the pivot of the row above it.
-
As a consequence, all the entries below a pivot are equal to zero.
-
A square matrix in row echelon form is upper triangular.
Gaussian elimination. Given \(\boldsymbol A \in \R^{m \times n}\), we process the columns from left to right. At each step, considering the rows not yet used as pivot rows:
-
find the first column containing a nonzero entry in these rows; if needed, bring such an entry to the top of these rows with a row swap \(R_k \leftrightarrow R_i\) (this nonzero entry is the pivot);
-
for each row \(i\) below the pivot row \(k\), create a zero below the pivot with the row addition
\[ R_i \leftarrow R_i - \frac{a_{ij}}{a_{kj}}\, R_k, \]where \(a_{kj}\) is the pivot and \(a_{ij}\) is the entry to be eliminated (in the current matrix);
-
repeat on the remaining rows.
At the end, the matrix is in row echelon form. Only row swaps and row additions are used.
Observation 1: Determinant by Gaussian elimination
Let \(\boldsymbol A \in \R^{n \times n}\) and let \(\boldsymbol U\) be a row echelon form of \(\boldsymbol A\) obtained by Gaussian elimination with \(s\) row swaps (and any number of row additions). Then
In particular, \(\det(\boldsymbol A) = 0\) if and only if \(\boldsymbol U\) has a zero on its diagonal.
Proof
Each row addition does not change the determinant and each row swap changes its sign. Hence \(\det(\boldsymbol U) = (-1)^{s}\det(\boldsymbol A)\), i.e., \(\det(\boldsymbol A) = (-1)^{s}\det(\boldsymbol U)\). Since \(\boldsymbol U\) is square and in row echelon form, it is upper triangular, and its determinant is the product of its diagonal entries. □
Example 13: Determinant by Gaussian elimination
Let us consider
We reduce \(\boldsymbol A\) to row echelon form with Gaussian elimination.
The matrix is now in row echelon form. We used \(s=1\) row swap, so
Indeed, by Laplace expansion along the first row: \(\det(\boldsymbol A) = 0\cdot(3-1) - 1\cdot(3-2) + 2\cdot(1-2) = -3\).
Try it in the lab
the same computation step by step: change the matrix and watch the steps change.
4. Pivoting and partial pivoting¶
-
In numerical algorithms such as matrix factorizations and row reduction methods, pivoting is a technique used to improve numerical stability and avoid division by zero.
-
The pivot element is the element used as the divisor in the elimination process.
4.1 Pivoting¶
Pivoting is the process of selecting a suitable pivot element in a matrix to perform elimination steps in row reduction algorithms.
When performing row elimination on a matrix \(\boldsymbol A \in \R^{n \times n}\), at step \(k\):
-
The pivot element is the entry \(a_{kk}\) (the diagonal element in position \((k,k)\)).
-
If \(a_{kk} = 0\), we cannot use it as a divisor, so we must swap row \(k\) with a row \(i > k\) such that \(a_{ik} \neq 0\).
-
This row swap is called pivoting.
Example 14: Pivoting in row elimination
Consider the matrix:
We cannot use \(a_{11} = 0\) as the first pivot. We need to swap row 1 with a row that has a nonzero element in the first column.
We swap rows 1 and 2 (i.e., \(R_1 \leftrightarrow R_2\)):
Now \(a_{11} = 1 \neq 0\) and we can proceed with the elimination:
Now we use \(a_{22} = 2\) as the second pivot:
The matrix is now in upper triangular form.
4.2 Partial pivoting¶
Partial pivoting is a strategy to improve numerical stability by choosing the largest available pivot in absolute value.
At step \(k\) of Gaussian elimination:
-
Find the row \(i \ge k\) such that \(|a_{ik}|\) is maximum among all \(|a_{jk}|\) for \(j \ge k\).
-
Swap row \(k\) with row \(i\) (i.e., \(R_k \leftrightarrow R_i\)).
-
Use the new \(a_{kk}\) as the pivot.
This ensures that:
-
The pivot is the largest element in absolute value in its column, among the entries on or below the diagonal.
-
Division by a larger number reduces round-off errors in floating-point arithmetic.
-
The method is numerically more stable.
Example 15: Partial pivoting in row elimination
Consider the matrix:
Step 1: Find the largest element in absolute value in the first column.
The maximum is \(|a_{21}| = 3\), so we swap rows 1 and 2:
Now eliminate below the pivot \(a_{11} = 3\):
Step 2: Find the largest element in absolute value in the second column (rows 2 and 3).
The maximum is \(\left|\frac{11}{3}\right|\), so we swap rows 2 and 3:
Eliminate below the pivot \(a_{22} = \frac{11}{3}\):
The matrix is now in upper triangular form (row echelon form).
Example 16: Comparison: without and with partial pivoting
Consider the matrix:
Without partial pivoting:
Using \(a_{11} = \frac{1}{10000}\) as the pivot:
This gives:
The large multiplier \(10000\) can cause significant round-off errors in floating-point arithmetic.
With partial pivoting:
Since \(|a_{21}| = 1 > |a_{11}| = \frac{1}{10000}\), we swap rows:
Now eliminate using \(a_{11} = 1\) as the pivot:
The multiplier \(\frac{1}{10000}\) is much smaller, leading to better numerical stability.
-
Partial pivoting is crucial in numerical linear algebra to ensure that algorithms produce accurate results, especially when dealing with matrices that have a wide range of magnitudes.
-
Most modern numerical software (such as MATLAB, NumPy, CPLEX, Gurobi) automatically uses partial pivoting in Gaussian elimination and LU factorization.
-
The computational cost of partial pivoting is minimal compared to the benefit of improved numerical stability.
Try it in the lab
the same computation step by step: change the matrix and watch the steps change.
Exercises and lab¶
- Exercises · the exercise sheet of this chapter: 10 exercises with worked solutions
- Lab · Gaussian elimination — Bring a matrix to row echelon (or reduced) form showing every elementary operation.
- Lab · Determinant — choose the «Gaussian elimination» method: the effect of each elementary operation on the determinant
- Lab · Why partial pivoting — The same system with and without partial pivoting, in floating point.