The document discusses the Gauss-Jordan elimination algorithm for computing the row-reduced echelon form (RREF) of a matrix A. The algorithm involves choosing pivots and using elementary row operations to transform A into an upper triangular matrix with leading coefficients of 1. An example applies the algorithm to compute the RREF of a sample matrix. Key points made include: 1) the RREF of a matrix is unique regardless of the order of pivots chosen; 2) if R=RREF(A) then R and A are row equivalent; and 3) systems with row equivalent coefficient matrices have the same solution set.
The document discusses the Gauss-Jordan elimination algorithm for computing the row-reduced echelon form (RREF) of a matrix A. The algorithm involves choosing pivots and using elementary row operations to transform A into an upper triangular matrix with leading coefficients of 1. An example applies the algorithm to compute the RREF of a sample matrix. Key points made include: 1) the RREF of a matrix is unique regardless of the order of pivots chosen; 2) if R=RREF(A) then R and A are row equivalent; and 3) systems with row equivalent coefficient matrices have the same solution set.
The document discusses the Gauss-Jordan elimination algorithm for computing the row-reduced echelon form (RREF) of a matrix A. The algorithm involves choosing pivots and using elementary row operations to transform A into an upper triangular matrix with leading coefficients of 1. An example applies the algorithm to compute the RREF of a sample matrix. Key points made include: 1) the RREF of a matrix is unique regardless of the order of pivots chosen; 2) if R=RREF(A) then R and A are row equivalent; and 3) systems with row equivalent coefficient matrices have the same solution set.
The document discusses the Gauss-Jordan elimination algorithm for computing the row-reduced echelon form (RREF) of a matrix A. The algorithm involves choosing pivots and using elementary row operations to transform A into an upper triangular matrix with leading coefficients of 1. An example applies the algorithm to compute the RREF of a sample matrix. Key points made include: 1) the RREF of a matrix is unique regardless of the order of pivots chosen; 2) if R=RREF(A) then R and A are row equivalent; and 3) systems with row equivalent coefficient matrices have the same solution set.
Linear Algebra through Matrices; Lecture 5, Part A, 07 April
Department of Mathematics and Statistics Indian Institute of Technology - Kanpur
Row Reduced Echelon Form (RREF) Continued
1 Gauss - Jordan Elimination
We now give an algorithm to compute the RREF and try to give a few applications. In general, the RREF has quite a lot of applications. Let A ∈ Mm,n (C). In the Gauss Elimination method, the idea was to get pivots and make every entry below the pivot as 0. Our task was to start from the (1, 1)-entry of the matrix and move to the bottom right. We now present an algorithm, commonly known as the Gauss-Jordan Elimination (GJE), to compute the RREF of A. 1. Input: A. 2. Output: a matrix B in RREF such that A is row equivalent to B. 3. Step 1: Put ‘Region’ = A. 4. Step 2: If all entries in the Region are 0, STOP. Else, in the Region, find the leftmost nonzero column and find its topmost nonzero entry. Suppose this nonzero entry is aij = c (say). Box it. This is a pivot. 5. Step 3: Interchange the row containing the pivot with the top row of the region. This column is called the pivotal column. Also, make the pivot entry 1 by dividing this top row by c. Use this pivot to make all other entries in the pivotal column as 0. 6. Step 4: Put Region = the submatrix below and to the right of the current pivot. Now, go to step 2. Important: The process will stop, as we can get at most min{m, n} pivots. 0 2 3 7 1 1 1 1 Example 1.1. Apply GJE algorithm to get RREF of 1 3 4 8 0 0 0 1 1. Region = A as A 6= 0. 1 1 1 1 1 1 1 1 0 2 3 7 0 2 3 7 2. Then, E12 A = 1 3 . Also, E31 (−1)E12 A = = B (say). 4 8 0 2 3 7 0 0 0 1 0 0 0 1 2
1 1 1 1 2 3 7 1 32 27 1 0 3. Now, Region = 2 3 7 6= 0. Then, E2 ( 2 )B = = C(say). Then, 0 2 3 7 0 0 1 0 0 0 1 1 0 −1 2 −5 2 0 3 7 1 2 2 E12 (−1)E32 (−2)C = 0 = D(say). 0 0 0 0 0 0 1 1 0 −12 −5 2 " # 3 7 0 0 0 1 2 2 4. Now, Region = . Then, E34 D = . Now, multiply on the left by 0 1 0 0 0 1 0 0 0 0 1 1 0 −2 0 0 3 1 0 E13 ( 52 ) and E23 ( −7 2 ) to get 0 2 , a matrix in RREF. Thus, A is row equivalent 0 0 1 0 0 0 0 1 1 0 −2 0 0 3 1 2 0 to F , where F = RREF(A) = . 0 0 0 1 0 0 0 0 5. Note that we have multiplied A on the left by the elementary matrices, E12 , E31 (−1), E2 (1/2), E32 −2, E12 (−1), E34 , E23 (−7/2), E13 (5/2), i.e.,
E13 (5/2)E23 (−7/2)E34 E12 (−1)E32 (−2)E2 (1/2)E31 (−1)E12 A = F = RREF(A).
6. Or equivalently, we have an invertible matrix P such that P A = F = RREF(A), where
Recall that a matrix A is in RREF if A is staircase/ ladder-like, all its pivots are 1 and every other entry in the pivotal column is 0.
Theorem 1.2. Let A be an m × n matrix and let R = RREF(A). Then
1. there exists elementary matrices, say E1 , . . . , Ek , such that R = E1 E2 · · · Ek A. 2. Let P = E1 E2 · · · Ek . Then R = P A with P −1 = (E1 E2 · · · Ek )−1 = Ek−1 Ek−1 −1 · · · E1−1 . So, if R = RREF (A) then there exists an invertible matrix P such that R = P A. This idea will be used again and again. 3. Thus, the matrices A and R are row-equivalent. 3
4. If A and B are row-equivalent then there exists an invertible matrix P such that P A = B.
Theorem 1.3. Consider the linear system Ax = b. If its augmented matrix [A b] is row equivalent to the matrix [C d] then the systems Ax = b and Cx = d have the same solution set. Thus, if A and B are two row equivalent matrices then, the systems Ax = 0 and Bx = 0 have the same solution set.
Important: Consider a matrix A of size m×n. Then the application of Gauss Elimination method to A may lead to different matrices depending on the pivots that each one of us have chosen. But, it turns out that what ever pivots we choose, the RREF (A) will be the same for all of us. That is, the RREF of a matrix is unique. We will use this idea in later classes.
