Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| numerical stability | Due to the limited precision of floating-point representations in actual computers, round-off errors in numerical computations may become amplified over the course of a computation, leading to incorrect results; such computations are numerically unstable.
(See page 723)
|
 |
|
|
| matrix | a rectangular array of numbers
(See page 726)
|
|
|
|
| transpose | The transpose of a matrix A is the matrix AT obtained by exchanging the rows and columns of A.
(See page 726)
|
|
|
|
| vector | a one-dimensional array of numbers.
(See page 726)
|
|
|
|
| column vector | The standard form of a vector, equivalent to an n x 1 matrix.
(See page 726)
|
|
|
|
| row vector | the transpose of a column vector.
(See page 726)
|
|
|
|
| unit vector | ei - the vector whose ith element is 1 and all of whose other elements are 0.
(See page 726)
|
|
|
|
| zero matrix | a matrix whose every entry is 0.
(See page 726)
|
|
|
|
| square | A square matrix is a n x n matrix
(See page 726)
|
|
|
|
| diagonal matrix | has aij = 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.
(See page 726)
|
|
|
|
| identity matrix | a diagonal matrix with 1's along the diagonal
(See page 727)
|
|
|
|
| tridiagonal matrix | matrix for which tij = 0 if |i - j| > 1. Nonzero entries appear only on the main diagonal, immediately above the main diagonal
(ti,j+1 for i = 1, 2, . . . , n - 1), or immediately below the main diagonal
(ti+1,j for i = 1, 2, . . . , n - 1).
(See page 727)
|
|
|
|
| upper-triangular matrix | one for which uij = 0 if i > j. All entries below the diagonal are zero.
(See page 727)
|
|
|
|
| unit upper-triangular | An upper-triangular matrix is unit upper-triangular if it has all 1's along the diagonal.
(See page 727)
|
|
|
|
| lower-triangular matrix | one for which lij = 0 if i < j. All entries above the diagonal are zero.
(See page 728)
|
|
|
|
| unit lower-triangular | A lower-triangular matrix is unit lower-triangular if it has all 1's along the diagonal.
(See page 728)
|
|
|
|
| permutation matrix | has exactly one 1 in each row or column, and 0's elsewhere. Called a permutation matrix because multiplying a vector x by a permutation matrix has the effect of permuting (rearranging) the elements of x.
(See page 728)
|
|
|
|
| symmetric matrix | satisfies the condition A = AT.
(See page 728)
|
|
|
|
| matrix addition | If A = (aij) and B = (bij) are m x n matrices, then their matrix sum
C = (cij) = A + B is the m x n matrix defined by cij = aij + bij for i = 1, 2, . . . , m and j = 1, 2, . . . , n. That is, matrix addition is performed componentwise.
(See page 728)
|
|
|
|
| scalar multiple | If λ is a number and A = (aij) is a matrix, then λA = (λaij) is the scalar multiple of A obtained by multiplying each of its elements by λ.
(See page 729)
|
|
|
|
| negative | As a special case, we define the negative of a matrix A = (aij) to be
-1 · A = -A, so that the ijth entry of -A is -aij. ThusA + (-A) = 0 = (-A) + A.
(See page 729)
|
|
|
|
| matrix subtraction | the addition of the negative of a matrix: A - B = A + (-B).
(See page 729)
|
|
|
|
| matrix multiplication | 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 in B. If A = (aij) is an m x n matrix and B = (bjk) is an n x p matrix, then their matrix product C = AB is the m x p matrix C = (cik).
(See page 729)
|
|
|
|
| (euclidean) norm | ||x|| of a vector x of size n is defined by ||x|| = (x12 + x22 + · · · + xn2)1/2 = (xTx)1/2. Thus, the norm of x is its length in n-dimensional euclidean space.
(See page 730)
|
|
|
|
| inverse | of an n x n matrix A is the n x n matrix, denoted A-1 (if it exists), such that AA-1 = In = A-1A. Many nonzero n x x matrices do not have inverses.
(See page 730)
|
|
|
|
| noninvertible, or singular | A matrix without an inverse.
(See page 730)
|
|
|
|
| invertible, or nonsingular | A matrix with an inverse.
(See page 730)
|
|
|
|
| linearly dependent | The vectors x1, x2, . . . , xn are linearly dependent if there exist coefficients c1, c2, . . . , cn, not all of which are zero, such that
c1x1 + c2x2 + · · · cnxn = 0.
(See page 731)
|
|
|
|
| linearly independent | vectors which are not linearly dependent. For example, the columns of an identity matrix are linearly independent.
(See page 731)
|
|
|
|
| column rank | of a nonzero m x n matrix A is the size of the largest set of linearly independent columns of A.
(See page 731)
|
|
|
|
| row rank | of A is the size of the largest set of linearly independent rows of A.
(See page 731)
|
|
|
|
| rank | 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 x 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 x n identity matrix is n.) An alternate, but equivalent and often more useful, definition is that the rank of a nonzero m x n matrix A is the smallest number r such that there exist matrices B and C of respective sizes m x r and r x n such that A = BC.
(See page 731)
|
|
|
|
| full rank | A square n x n matrix has full rank if its rank is n.
(See page 731)
|
|
|
|
| full column rank | An m x n matrix has full column rank if its rank is n.
(See page 731)
|
|
|
|
| null vector | for a matrix A is a nonzero vector x such that Ax = 0.
(See page 731)
|
|
|
|
| minor | The ijth minor of an n x n matrix A, for n > 1, is the (n - 1) x (n - 1) matrix A[ij] obtained by deleting the ith row and jth column of A.
(See page 732)
|
|
|
|
| positive definite | An n x n matrix A is positive-definite if xTAx > 0 of all size-n vectors
x ≠ 0.
(See page 732)
|
|
|
|
| essential term | one of the eight terms appearing on the right-hand side of one of the equations (28.9)-(28.12).
(See page 738)
|
|
|
|
| solution | A set of values for x1, x2, . . . , xn that satisfy all of the equations simultaneously.
(See page 742)
|
|
|
|
| underdetermined | If the number of equations is less than the number n of unknowns - or, more generally, if the rank of A is less than n. An underdetermined system typically has infinitely many solutions, although it may have no solutions at all if the equations are inconsistent.
(See page 743)
|
|
|
|
| overdetermined | If the number of equations exceeds the number n of unknowns. There may not exist any solutions.
(See page 743)
|
|
|
|
| LUP decomposition | The idea behind LUP decomposition is to find three n x n matrices L, U, and P such that P A = LU, where · L is a unit lower-triangular matrix, · U is an upper-triangular matrix, and · P is a permutation matrix. We call matrices L, U, and P satisfying the equation P A = LU an LUP decomposition of the matrix A.
(See page 743)
|
|
|
|
| LU decomposition | If an LUP decomposition can be computed for a non-singular matrix A, forward and back substitution can be used to solve the system Ax = b of linear equations. To show how an LUP decomposition for A can be found efficiently, we start with the case in which A is an n x n nonsingular matrix and P is absent (or, equivalently, P = In). In this case, we must find a factorization A = LU. We call the matrices L and U and LU decomposition of A.
(See page 747)
|
|
|
|
| Gaussian elimination | The process which performs LU decomposition.
(See page 747)
|
|
|
|
| pivots | The elements by which we divide during LU decomposition. They occupy the diagonal elements of the matrix U.
(See page 749)
|
|
|
|
| pivoting | using permutations to avoid division by 0 (or by small numbers).
(See page 749)
|
|
|
|
| conjugate transpose | A* - obtained from the transpose of A by replacing every entry with its complex conjugate.
(See page 759)
|
|
|
|
| Hermitian | matrices such that A = A*.
(See page 759)
|
|
|
|
| leading submatrix | The kth leading submatrix of A is the matrix Ak consisting of the intersection of the first k rows and first k columns of A.
(See page 760)
|
|
|
|
| approximation errors | η = Ac - y is the size-m vector of approximation errors.
(See page 763)
|
|
|
|
| singular value decomposition | SVD - an m x n matrix A is factored into A = Q1ΕQ2T, where Ε is an
m x n matrix with nonzero values only on the diagonla, Q1 is m x m with mutually orthonormal columns, and Q2 is n x n, also with mutually orthonormal columns.
(See page 769)
|
|
|
|
| orthonormal | Two vectors are orthonormal if their inner product is 0 and each vector has a norm of 1.
(See page 769)
|
2002 McGraw-Hill Higher Education