Appendix D: Matrices

Matrices arise in numerous applications, including scientific computing. This appendix covers basic matrix definitions, operations, and fundamental properties.

---

D.1 Matrices and Matrix Operations

Matrices and Vectors

• A matrix is a rectangular array of numbers. For example, a 2 × 3 matrix:

A = | 1  2  3 |
    | 4  5  6 |

• We denote the element in row i and column j by a_ij
• Uppercase letters denote matrices; subscripted lowercase letters denote their elements
• R^(m×n) denotes the set of all m × n matrices with real-valued entries
• More generally, S^(m×n) denotes the set of m × n matrices with entries drawn from a set S

Transpose

• The transpose of a matrix A is the matrix A^T obtained by exchanging the rows and columns of A
• If A is m × n, then A^T is n × m

Vectors

• A vector is a one-dimensional array of numbers
• A vector of length n is called an n-vector
• The standard form of a vector is a column vector (an n × 1 matrix)
• A row vector is obtained by taking the transpose: x^T
• The unit vector e_i is the vector whose i-th element is 1 and all other elements are 0
• A zero matrix is a matrix whose entries are all 0, often denoted 0

Square Matrices

Square n × n matrices arise frequently. Important special cases:

1. Diagonal matrix: a_ij = 0 whenever i ≠ j. Written as diag(a₁₁, a₂₂, ..., a_nn). Only the diagonal entries may be nonzero.

2. Identity matrix I_n: a diagonal matrix with 1s along the diagonal.

   • I_n = diag(1, 1, ..., 1)
   • The i-th column of an identity matrix is the unit vector e_i

3. Tridiagonal matrix T: t_ij = 0 if |i − j| > 1. Nonzero entries appear only on:

   • The main diagonal
   • Immediately above the main diagonal (t_{i, i+1})
   • Immediately below the main diagonal (t_{i+1, i})

4. Upper-triangular matrix U: u_ij = 0 if i > j. All entries below the diagonal are zero.

   • A unit upper-triangular matrix has all 1s along the diagonal

5. Lower-triangular matrix L: l_ij = 0 if i < j. All entries above the diagonal are zero.

   • A unit lower-triangular matrix has all 1s along the diagonal

6. Permutation matrix P: has exactly one 1 in each row and each column, and 0s elsewhere.

   • Multiplying a vector x by P permutes (rearranges) the elements of x

7. Symmetric matrix A: satisfies A = A^T

Basic Matrix Operations

Matrix Addition:

• If A = (a_ij) and B = (b_ij) are m × n matrices, then C = A + B is defined by c_ij = a_ij + b_ij
• Addition is performed componentwise
• A zero matrix is the identity for matrix addition: A + 0 = A = 0 + A

Scalar Multiplication:

• If λ is a number and A = (a_ij), then λA = (λ · a_ij)
• The negative of a matrix: −A = (−1) · A
• A + (−A) = 0

Matrix Subtraction:

• A − B = A + (−B)

Matrix Multiplication:

• Requires compatible matrices: the number of columns of A must equal the number of rows of B
• If A is m × n and B is n × p, then C = AB is the m × p matrix where:

c_ij = Σ (k=1 to n) a_ik · b_kj

• SQUARE-MATRIX-MULTIPLY runs in Θ(n³) time (n³ multiplications and n²(n−1) additions)

Key Algebraic Properties:

• Identity: I_m · A = A · I_n = A for any m × n matrix A
• Zero: A · 0 = 0
• Associative: A(BC) = (AB)C
• Distributive: A(B + C) = AB + AC and (B + C)D = BD + CD
• Not commutative in general (for n > 1): AB ≠ BA

Matrix-Vector and Vector-Vector Products

• If A is m × n and x is an n-vector, then Ax is an m-vector
• Inner product (dot product) of n-vectors x and y:

x^T y = Σ (i=1 to n) x_i · y_i

This produces a scalar (1 × 1 matrix)

• Outer product of n-vectors x and y: the n × n matrix Z = xy^T, where z_ij = x_i · y_j

• Euclidean norm of an n-vector x:

‖x‖ = (x₁² + x₂² + ... + xₙ²)^(1/2) = (x^T x)^(1/2)

The norm is the length of x in n-dimensional Euclidean space

---

D.2 Basic Matrix Properties

Matrix Inverses

• The inverse of an n × n matrix A is the n × n matrix A⁻¹ (if it exists) such that:

  • AA⁻¹ = I_n = A⁻¹A

• A matrix without an inverse is called noninvertible (or singular)

• A matrix with an inverse is called invertible (or nonsingular)

• Matrix inverses, when they exist, are unique

Key inverse properties:

• If A and B are nonsingular n × n matrices: (BA)⁻¹ = A⁻¹B⁻¹
• The inverse commutes with the transpose: (A⁻¹)^T = (A^T)⁻¹

Linear Dependence and Independence

• Vectors x₁, x₂, ..., x_n are linearly dependent if there exist coefficients c₁, c₂, ..., c_n (not all zero) such that:
  • c₁x₁ + c₂x₂ + ... + c_nx_n = 0
• If vectors are not linearly dependent, they are linearly independent
• Example: the columns of an identity matrix are linearly independent

Rank

• The column rank of a nonzero m × n matrix A is the size of the largest set of linearly independent columns of A
• The row rank is the size of the largest set of linearly independent rows of A
• Fundamental property: row rank always equals column rank, so we simply refer to the rank of A
• The rank of an m × n matrix is an integer between 0 and min(m, n), inclusive
  • Rank of a zero matrix = 0
  • Rank of an n × n identity matrix = n
• Alternate definition: the rank of a nonzero m × n matrix A is the smallest number r such that there exist matrices B (m × r) and C (r × n) with A = BC
• A square n × n matrix has full rank if its rank is n
• An m × n matrix has full column rank if its rank is n

Theorem D.1: A square matrix has full rank if and only if it is nonsingular.

Null Vectors

• A null vector for a matrix A is a nonzero vector x such that Ax = 0

Theorem D.2: A matrix A has full column rank if and only if it does not have a null vector.

Corollary D.3: A square matrix A is singular if and only if it has a null vector.

Determinants

• The determinant of an n × n matrix A is defined recursively:

det(A) = a₁₁                                    if n = 1
det(A) = Σ (j=1 to n) (-1)^(1+j) · a₁ⱼ · det(A[1j])   if n > 1

• A[ij] is the (i,j)-th minor: the (n−1) × (n−1) matrix obtained by deleting row i and column j
• The term (−1)^(i+j) · det(A[ij]) is the cofactor of element a_ij

Theorem D.4 (Determinant Properties):

1. If any row or column of A is zero, then det(A) = 0
2. Multiplying all entries of one row (or column) by λ multiplies det(A) by λ
3. Adding one row (or column) to another leaves det(A) unchanged
4. det(A) = det(A^T)
5. Exchanging any two rows (or columns) multiplies det(A) by −1
6. For any square matrices A and B: det(AB) = det(A) · det(B)

Theorem D.5: An n × n matrix A is singular if and only if det(A) = 0.

---

Positive-Definite Matrices

• An n × n matrix A is positive-definite if x^T A x > 0 for all n-vectors x ≠ 0

• Example: the identity matrix is positive-definite, since for any nonzero vector x:

x^T I_n x = x^T x = Σ (i=1 to n) x_i² > 0

Theorem D.6: For any matrix A with full column rank, the matrix A^T A is positive-definite.

Proof sketch:

• For any vector x: x^T(A^T A)x = (Ax)^T(Ax) = ‖Ax‖²
• Since ‖Ax‖² is the sum of squares of elements of Ax, we have ‖Ax‖² ≥ 0
• If ‖Ax‖² = 0, then Ax = 0, which implies x = 0 (since A has full column rank, by Theorem D.2)
• Therefore x^T(A^T A)x > 0 for all nonzero x, so A^T A is positive-definite

---

Summary of Key Relationships