Elementary Matrix Operations

• Let . The following operations on the rows or columns of are called elementary row / column operators

  • Interchanging any two rows / columns of .
  • Multiplying any row / column of by a nonzero constant.
  • Adding any constant multiple of a row / column of to another row / column of

• An elementary matrix is a matrix obtained by performing on .

  • Type 1: Interchange two rows / columns of
  • Type 2: Multiply any row / column of by a nonzero constant.
  • Type 3: Adding any constant multiple of a row / column to another.

• (Friedberg 3.1) Row variant: Let and suppose that is obtained from by performing an elementary row operation. Then there exists an elementary matrix such that . In fact is obtained by performing the corresponding row operation on . Conversely, if is an elementary matrix, then is a matrix that can be obtained by performing an elementary row operation on .

  Column Variant: Let and suppose that is obtained from by performing an elementary column operation. Then there exists an elementary matrix such that . In fact is obtained by performing the corresponding column operation on . Conversely, if is an elementary matrix, then is a matrix that can be obtained by performing an elementary column operation on .

• (Friedberg 3.2) Elementary matrices are invertible. Their inverse is an elementary matrix of the same type.

• (Friedberg 3.4.1) Elementary row and column operations on a matrix are rank-preserving.

• (Friedberg 3.6) Let such that . Then and by means of a finite number of elementary row and column operators can be transformed into a matrix such that

  • (Friedberg 3.6.1) Let such that . Then there exists invertible matrices and respectively such that , where is the matrix in (Friedberg 3.6)
  • (Friedberg 3.6.3) An invertible matrix is a product of elementary matrices.

Systems of Linear Equations §

• A system of linear equations of the form

  Can be represented compactly using an matrix

  And vectors

  So that we are solving

  Or more specifically, finding such that

  We refer to the above as a system of linear equations

• A system of equations in unknowns is homogeneous if and non-homogeneous otherwise.

  Any homogeneous system has at least one solution, namely the trivial solution of all ‘s.

• (Friedberg 3.8) Let be a homogeneous system of linear equations in unknowns over field . Let denote the set of all solutions to . Then

  And also

  And

• (Friedberg 3.8.1) If , then has a nontrivial solution.

• (Friedberg 3.9) Let be the solution set of a system of linear equations , and be the solution set of the corresponding homogeneous system . Then for any solution

  ¹

• (Friedberg 3.10) Let be a system of equations in unknownsn. If is invertible, then the system has exactly one solution — .

  Conversely, if the system has exactly one solution then is invertible.

• (Friedberg 3.11) Let be a system of linear equations. Then the system has at least one solution if and only if

• (Friedberg 3.12) A system has a solution if and only if

• Two systems of linear equations in unknowns are equivalent if they have the same solution set.

• (Friedberg 3.13) Let be a system of linear equations in unknowns and let be any invertible matrix. Then the system is equivalent to .

• (Friedberg 3.13.1) If is obtained from by a finite number of elementary row operations, then the system is equivalent to the original system

• To solve a linear system of equations, we use the associated matrix and using elementary row operations, reduce it to row echelon form. That is:

  • Any row containing a nonzero entry precedes any row in which all the entries are zero (if any)
  • The first nonzero entry in each row is the only nonzero entry in its column.
  • The first nonzero entry in each row is and it occurs in a column to the right of the leading in any preceding column

• (Friedberg 3.14) We can transform a matrix to row echelon form using Gaussian Elimination

  • Transform the augmented matrix into an upper triangular matrix.
  • Using backwards substitution, transform the upper triangular matrix to row echelon form.

• Gaussian Elimination transforms a matrix to row echelon form using the fewest arithmetic operations

• (Friedberg 3.15) Let be a system of nonzero equations in unknowns. Suppose and is in row echelon form.

  • If the general solution is of the form
    Then is basis for the solution set of the corresponding homogeneous system and is a solution in the original system.

• The method for solving systems of linear equations can be phrased as applying a division algorithm process repeatedly to change a given ideal basis into one that better illustrates the geometry of the associated algebraic variety.

• (Friedberg 6.37) For the system , where is invertible and , we have the following (see more on the condition number here).

  • For any norm .
  • Let and be the largest and smallest eigenvalues of (see more here).

Links §

• Friedberg, Insel and Spence
• Matrix

Footnotes §

1. Vector Sum and Direct Sum. An analogy from Group Theory can be made: Define the homomorphism as the one associated with the linear transformation . Then and what we are saying is that any solution has an associated family of solutions (i.e., entire cosets). ↩