Linear Algebra

An mxn linear system Ax = b is a system of m linear equations in n unknowns x_i  , i=1,...,n.
If the linear system has a solution it is consistent, otherwise it is inconsistent.
Ax = 0 is a homogeneous linear system.
The homogeneous linear system always has the  trivial solution x = 0.

The linear systems Ax = b and Cx = d are equivalent, if they both have exactly the same solutions.

Def 1.1: An mxn  matrix A is a rectangular array of mn real or complex numbers arranged in m horizontal rows and n vertical columns.
Def 1.2: Two mxn matrices A=[a_ij] and B=[b_ij] are equal, if they agree entry by entry.
Def 1.3: The mxn matrices A and B are added entry by entry.
Def 1.4: If A=[a_ij] and r is a real number then the scalar multiple of A is the matrix  rA=[ra_ij].
If A₁, A₂, ..., A_k are mxn matrices and c₁, c₂, ..., c_k are real numbers then an expression of the form
            c₁A₁ + c₂A₂ + ... + c_kA_k
        is a linear combination of the A's with coefficients c₁, c₂, ..., c_k .
Def 1.5: The transpose of the mxn matrix A=[a_ij] is the nxm matrix A^T=[a_ji].
Def 1.6: The dot product or inner product of the n-vectors a=[a_i] and b=[b_i] is  ab = a₁b₁ + a₂b₂ + ... + a_nb_n.
Def 1.7: If A=[a_ij] is an mxp matrix and B=[b_ij] a pxn matrix they can be multiplied and the ij entry of the mxn C = AB:
                c_ij = dot product of the (ith row of A)^T with (jth column of B).

Note:  Ax = b is consistent if and only if b can be expressed as a linear combination of the columns of A with coefficients x_i.

Theorem 1.1 Let A, B, and C be mxn matrices, then
            (a)    A + B = B + A
            (b)    A + (B + C) = (A + B) + C
            (c)    there is a unique mxn matrix O such that for any mxn matrix A
                    A + O = A
            (d)    for each mxn matrix A, there is aunique mxn matrix D such that
                    A + D = O
                    D = -A is the negative of A.

Theorem 1.2  Let A, B, and C be matrices of the appropriate sizes, then
            (a)    A(BC) = (AB)C
            (b)    (A + B)C = AC + BC
            (c)    C(A + B) = CA + CB

Theorem 1.3 Let r, s be real numbers and A, B matrices of the appropriate sizes, then
            (a)    r(sA) = (rs)A
            (b)   (r + s)A = rA + sA
            (c)    r(A + B) = rA + rB
            (d)    A(rB) = r(AB) = (rA)B

Theorem 1.4  Let r be a scalar, A, B matrices of appropriate sizes, then
            (a)    (A^T)^T =A
            (b)    (A + B)^T = A^T + B^T
            (c)    (AB)^T = B^TA^T
            (d)    (rA)^T = rA^T

Note:
           (a) AB need not equal BA
           (b) AB may be the zero matrix with A not equal O and B not equal O
           (c) AB may equal AC with B not equal C

Def 1.8:  A matrix A with real enties is symmetric if  A^T = A.
Def 1.9: A matrix with real entries is skewsymmetric if  A^T = -A.
             An nxn matrix A is upper triangular if a_ij = 0 for i > j, lower triangular if a = 0 for i < j.
Def 1.10:  An nxn matrix A is nonsingular or invertible, if there exists an nxn matrix B such that
            AB = BA = I_n
            B would then be the inverse of A
            Otherwise A is singular or noninvertible.

Theorem 1.5  The inverse of a matrix, if it exists is unique.
Theorem 1.6  If A and B are both nonsingular nxn matrices then AB is nonsingular and (AB)^-1 = B^-1A^-1.
Corollary 1.1 If A₁, A₂, ..., A_r are nonsingular nxn matrices, then A₁A₂ ...A_r is nonsingular and (A₁A₂ ...A_r)^-1 = A_r^-1... A₂^-1A₁^-1.
Theorem 1.7  If A is a nonsingular matrix, then A^-1 is nonsingular and  (A^-1)^-1 = A.
Theorem 1.8  If A is a nonsingular matrix, then A^T is nonsingular and  (A^-1)^T = (A^T)^-1.

Note:  If A is a nonsingular nxn matrix. Then
            (a)    the linear system Ax = b has the unique solution  x = A^-1b.
            (b)    the homogeneous linear system Ax = 0 has the unique solution x = 0.

Def 2.1 An mxn matrix is said to be in reduced row echelon form if it satisfiesthe following properties:
            (a)    all zero rows, if there are any, are at the bottom of the matrix.
            (b)    the first nonzero entry from the left of a nonzero row is a 1.This entry is called a leading one of its row.
            (c)    For each nonzero row, the leading one appears to the right and below any leading ones in preceding rows.
            (d)    If a column contains a leading one, then all other entries in that column are zero.
            An mxn matrix is in row echelon form, if it satisfies properties (a), (b), and (c).
            Similar definition for column echelon form.
Def 2.2  An elementary row (column) operation on a matrix A is one of these:
            (a)    interchange of two rows
            (b)    multiply a row by a nonzero number
            (c)    add a multiple of one row to another.
Def 2.3  An mxn matrix B is row (column) equivalent to an mxn matrix A, if B can be produced by applying a finite sequence of elementary row (column) operations to A.

Theorem 2.1    Every nonzero mxn matrix A = [a_ij] is row (column) equivalent to a matrix in row (column) echelon form.
Theorem 2.2    Every nonzero mxn matrix A = [a_ij] is row (column) equivalent to a unique matrix in reduced (column) row echelon form.
Theorem 2.3    Let Ax = b and Cx = d be two linear systems, each of m equations in n unknowns. If the augmented matrices [A | b] and [C | d] are row equivalent, then the linear systems are equivalent, i.e. they have exactly the same solutions.
Theorem 2.4   A homogeneous system of m linear equations in n unknowns always has a nontrivial solution if m<n, that is, if the number of unknowns exceeds the number of equations.

Gaussian elimination: transform [A | b] to [C | d], where {C | d] is in row echelon form.
Gauss Jordan reduction: transform [A | b] to [C | d], where {C | d] is in reduced row echelon form.

Def 2.4  an elementary matrix is a matrix obtained from the identity matrix by performing a single elementary row operation.

Theorem 2.5    Perform an elementary row operation (with matrix E) on mxn matrix A to yield matrix B. Then B = EA.
Theorem 2.6    Let A, B be mxn matrices. Equivalent:
            (a)    A is row equivalent to B.
            (b)    There exist elementary matrices E₁, E₂, ..., E_k, such that  B = E_kE_{k - 1}...E₁A.
Theorem 2.7    An elementary matrix E is nonsingular, and its inverse is an elementary matrix of the same type.
Lemma 2.1    Let A be an nxn matrix and suppose the homogeneous system Ax = 0 has only the trivial solution x = 0. Then A is row equivalent to I_n.
Theorem 2.8    A is nonsingular if and only if A is the product of elementary matrices.
Corollary 2.2    A is nonsingular if and only if A is row equivalent to I_n.
Theorem 2.9    Equivalent:
            (a)    The homogeneous system of n linear equations in n unknowns  Ax = 0 has a nontrivial solution.
            (b)    A is singular.
Theorem 2.10    Equivalent:
            (a)    nxn matrix A is singular .
            (b)    A is row equivalent to a matrix that has a row of zeroes.
Theorem 2.11    Let A, B be nxn matrices such that  AB = I_n, then BA = I_n and B = A^-1.

Def 2.5   A, B mxn matrices. A is equivalent to B, if we can obtain D from A by a finite sequence of elementary row  and column operations.

Theorem 2.12    If  A is a nonzero mxn matrix, then A is equivalent to a partitioned matrix of the form:

Def 3.1    Let S = {1, 2, ..., n} in this order. A rearrangement  j₁j₂ ...j_n  of the elements of S is a permutation of S.
Def 3.2    Let A = [a_ij] be an nxn matrix. The determinant function det is defined by

Theorem 3.1    If A is a matrix, then  det(A) = det(A^T).
Theorem 3.2    If matrix B results from matrix A by interchanging two different rows(columns) of A, then  det(B) = - det(A).
Theorem 3.3    If two rows (columns) of A are equal, then det(A) = 0.
Theorem 3.4    If a row (column) of A consists entirely of zeros, then det(A) = 0.
Theorem 3.5    If B is obtained from A by multiplying a row (column) of A by a real number k, then det(B) = k det(A).
Theorem 3.6    If B = [b_ij] is obtained from A = [a_ij] by adding to each element of the sth (column) r ≠ s, of A, then det(B) = det(A).
Theorem 3.7    If a matrix A = [a] is upper(lower) triangular, then det(A) = a₁₁a₂₂ ...a_nn; that is the determinant of a triangular matrix is the product of the elements on the main diagonal.
Lemma 3.1     If E is an elementary matrix, then det(EA) = det(E)det(A), and det(AE) = det(A)det(E)..
Theorem 3.8    If A is an nxn matrix, equivalent
            (a)    A is nonsingular
            (b)    det(A) ≠ 0.
.Corollary 3.1    A an nxn matrix. Equivalent:
            (a)    Ax = 0  has a nontrivial solution.
            (b)    det(A) = 0.
Theorem 3.9     If  A, B are nxn matrices, then det(AB) = det(A)det(B).
Corollary 3.2    If  A  is nonsingular, then det(A^-1) = 1/(det(A)).

Def 6.6    Matrices A, B  are similar, if there is a nonsingular matrix P, such that  B = P^-1AP.

Corollary 3.3    If  A, B are similar matrices, then det(A) = det(B).
  Def 3.3    Let A = [a_ij]  be an nxn matrix. Let M_ij  be the (n-1)x(n-1) submatrix of A obtained by deleting the ith row and the jth column of A. The determinant det(M_ij) is called the minor of a_ij.
Def 3.4    Let A = [a_ij]  be an nxn matrix. The cofactor A_ij  of a_ij  is defined as  A_ij = (-1^i+j) det(M_ij).

Theorem 3.10   Let A = [a_ij]  be an nxn matrix. Then

• det(A) = a_i1A_i1 + a_i2A_i2 + ... + a_inA_in            (expansion along ith row)
• det(A) = a_1jA_1j + a_2jA_2j + ... + a_njA_nj            (expansion along jth column)

• a_i1A_k1 + a_i2A_k2 + ... + a_inA_kn = 0 for  i ≠ k
• a_1jA_1k + a_2jA_2k + ... + a_njA_nk = 0 for j ≠ k

Theorem 3.12    Let A = [a_ij] be an nxn matrix, then  A(adj A) = (adj A)A = det(A)I_n.
Corollary 3.4    Let A be an nxn matrix and det(A) ≠ 0, then    A^-1 = 1/(det A) * (adj A).
Theorem 3.13    Cramer's Rule     Let  A be an nxn matrix  and Ax = b and det A ≠ 0, then the system has the unique solution
         x₁ = (det A₁)/(det A),   x₂ = (det A₂)/(det A),  ... ,   x_n = (det A_n)/(det A),
        where A_i is the matrix obtained from A by replacing the ith column of A  by b.