Matrices and vectors

A matrix is a rectangular array of numbers. For example,

is a 2 × 3 matrix A = (a_ij), where for i = 1, 2 and j = 1, 2, 3, the element of the matrix in row i and column j is a_ij. We use uppercase letters to denote matrices and corresponding subscripted lowercase letters to denote their elements. The set of all m × n matrices with real-valued entries is denoted R^m×n. In general, the set of m × n matrices with entries drawn from a set S is denoted S^m×n.

The transpose of a matrix A is the matrix A^T obtained by exchanging the rows and columns of A. For the matrix A of equation (28.1),

A vector is a one-dimensional array of numbers. For example,

is a vector of size 3. We use lowercase letters to denote vectors, and we denote the ith element of a size-n vector x by x_i , for i = 1, 2, . . . , n. We take the standard form of a vector to be as a column vector equivalent to an n × 1 matrix; the corresponding row vector is obtained by taking the transpose:

x^T = (2 3 5).

The unit vector e_i is the vector whose ith element is 1 and all of whose other elements are 0. Usually, the size of a unit vector is clear from the context.

A zero matrix is a matrix whose every entry is 0. Such a matrix is often denoted 0, since the ambiguity between the number 0 and a matrix of 0's is usually easily resolved from context. If a matrix of 0's is intended, then the size of the matrix also needs to be derived from the context.

Square n × n matrices arise frequently. Several special cases of square matrices are of particular interest:

1. A diagonal matrix has a_ij = 0 whenever i ≠ j. Because all of the off-diagonal elements are zero, the matrix can be specified by listing the elements along the diagonal:

   

2. The n × n identity matrix I_n is a diagonal matrix with 1's along the diagonal:

   

   When I appears without a subscript, its size can be derived from context. The ith column of an identity matrix is the unit vector e_i.

3. A tridiagonal matrix T is one for which t_ij = 0 if |i - j| > 1. Nonzero entries appear only on the main diagonal, immediately above the main diagonal (t_i,i+1 for i = 1, 2, . . . , n - 1), or immediately below the main diagonal (t_i+1,i for i = 1, 2, . . . , n - 1):

   

4. An upper-triangular matrix U is one for which u_ij = 0 if i > j. All entries below the diagonal are zero:

   

   An upper-triangular matrix is unit upper-triangular if it has all 1's along the diagonal.

5. A lower-triangular matrix L is one for which l_ij = 0 if i < j. All entries above the diagonal are zero:

   

   A lower-triangular matrix is unit lower-triangular if it has all 1's along the diagonal.

6. A permutation matrix P has exactly one 1 in each row or column, and 0's elsewhere. An example of a permutation matrix is

   

   Such a matrix is called a permutation matrix because multiplying a vector x by a permutation matrix has the effect of permuting (rearranging) the elements of x.

7. A symmetric matrix A satisfies the condition A = A^T. For example,

   

   is a symmetric matrix.

Operations on matrices

The elements of a matrix or vector are numbers from a number system, such as the real numbers, the complex numbers, or integers modulo a prime. The number system defines how to add and multiply numbers. We can extend these definitions to encompass addition and multiplication of matrices.

We define matrix addition as follows. If A = (a_ij) and B = (b_ij) are m × n matrices, then their matrix sum C = (c_ij) = A + B is the m × n matrix defined by

c_ij = a_ij + b_ij

for i = 1, 2, . . . , m and j = 1, 2, . . . , n. That is, matrix addition is performed componentwise. A zero matrix is the identity for matrix addition:

If λ is a number and A = (a_ij) is a matrix, then λA = (λa_ij) is the scalar multiple of A obtained by multiplying each of its elements by λ. As a special case, we define the negative of a matrix A = (a_ij) to be -1 · A = - A, so that the ijth entry of -A is -a_ij. Thus,

Given this definition, we can define matrix subtraction as the addition of the negative of a matrix: A - B = A + (-B).

We define matrix multiplication as follows. We start with two matrices A and B that are compatible in the sense that the number of columns of A equals the number of rows of B. (In general, an expression containing a matrix product AB is always assumed to imply that matrices A and B are compatible.) If A = (a_ij) is an m × n matrix and B = (b_jk) is an n × p matrix, then their matrix product C = AB is the m × p matrix C = (c_ik), where

for i = 1, 2, . . . , m and k = 1, 2, . . . , p. The procedure MATRIX-MULTIPLY in Section 25.1 implements matrix multiplication in the straightforward manner based on equation (28.3), assuming that the matrices are square: m = n = p. To multiply n × n matrices, MATRIX-MULTIPLY performs n³ multiplications and n²(n - 1) additions, and so its running time is Θ(n³).

Matrices have many (but not all) of the algebraic properties typical of numbers. Identity matrices are identities for matrix multiplication:

I_m A = AI_n = A

for any m × n matrix A. Multiplying by a zero matrix gives a zero matrix:

A 0 = 0.

Matrix multiplication is associative:

for compatible matrices A, B, and C. Matrix multiplication distributes over addition:

For n > 1, multiplication of n × n matrices is not commutative. For example, if and , then

and

Matrix-vector products or vector-vector products are defined as if the vector were the equivalent n × 1 matrix (or a 1 × n matrix, in the case of a row vector). Thus, if A is an m × n matrix and x is a vector of size n, then Ax is a vector of size m. If x and y are vectors of size n, then

is a number (actually a 1 × 1 matrix) called the inner product of x and y. The matrix xy^T is an n×n matrix Z called the outer product of x and y, with z_ij = x_i y_j. The (euclidean) norm ∥x∥ of a vector x of size n is defined by

Thus, the norm of x is its length in n-dimensional euclidean space.

Matrix inverses, ranks, and determinants

We define the inverse of an n × n matrix A to be the n × n matrix, denoted A^-1 (if it exists), such that AA^-1 = I_n = A^-1 A. For example,

Many nonzero n × n matrices do not have inverses. A matrix without an inverse is called noninvertible, or singular. An example of a nonzero singular matrix is

If a matrix has an inverse, it is called invertible, or nonsingular. Matrix inverses, when they exist, are unique. (See Exercise 28.1-3.) If A and B are nonsingular n × n matrices, then

The inverse operation commutes with the transpose operation:

(A^-1)^T = (A^T)^-1.

The vectors x₁, x₂, . . . , x_n are linearly dependent if there exist coefficients c₁, c₂, . . . , c_n, not all of which are zero, such that c₁x₁ + c₂x₂ + · · · + c_n x_n = 0. For example, the row vectors x₁ = (1 2 3 ), x₂ = (2 6 4), and x₃ = (4 11 9) are linearly dependent, since 2x₁ + 3x₂ - 2x₃ = 0. If vectors are not linearly dependent, they are linearly independent. For example, the columns of an identity matrix are linearly independent.

The column rank of a nonzero m × n matrix A is the size of the largest set of linearly independent columns of A. Similarly, the row rank of A is the size of the largest set of linearly independent rows of A. A fundamental property of any matrix A is that its row rank always equals its column rank, so that we can simply refer to the rank of A. The rank of an m × n matrix is an integer between 0 and min(m, n), inclusive. (The rank of a zero matrix is 0, and the rank of an n × n identity matrix is n.) An alternate, but equivalent and often more useful, definition is that the rank of a nonzero m × n matrix A is the smallest number r such that there exist matrices B and C of respective sizes m × r and r × n such that

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. A fundamental property of ranks is given by the following theorem.

A null vector for a matrix A is a nonzero vector x such that Ax = 0. The following theorem, whose proof is left as Exercise 28.1-9, and its corollary relate the notions of column rank and singularity to null vectors.

The ijth minor of an n × n matrix A, for n > 1, is the (n-1) × (n-1) matrix A_[ij] obtained by deleting the ith row and jth column of A. The determinant of an n × n matrix A can be defined recursively in terms of its minors by

The term (-1)^i+j det(A_[ij]) is known as the cofactor of the element a_ij.

The following theorems, whose proofs are omitted here, express fundamental properties of the determinant.

Positive-definite matrices

Positive-definite matrices play an important role in many applications. An n × n matrix A is positive-definite if x^T Ax > 0 for all size-n vectors x ≠ 0. For example, the identity matrix is positive-definite, since for any nonzero vector x = (x₁ x₂ · · · x_n)^T,

As we shall see, matrices that arise in applications are often positive-definite due to the following theorem.

Other properties of positive-definite matrices will be explored in Section 28.5.