GLOSSARY: A DICTIONARY FORLINEAR ALGEBRAAdjacency matrix of a graph. Square matrix with aij= 1 when there is an edge from nodei to node j; otherwise aij= 0. A = ATfor an undirected graph.Affine transformation T (v) = Av + v0= linear transformation plus shift.Associative Law (AB)C = A(BC). Parentheses can be removed to leave ABC.Augmented matrix [ A b ]. Ax = b is solvable when b is in the column space of A; then[ A b ] has the same rank as A. Elimination on [ A b ] keeps equations correct.Back substitution. Upper triangular systems are solved in reverse order xnto x1.Basis for V . Independent vectors v1, . . . , vdwhose linear combinations give every v inV . A vector space has many bases!Big formula for n by n determinants. Det(A) is a sum of n! terms, one term for eachpermutation P of the columns. That term is the product a1α···anωdown thediagonal of the reordered matrix, times det(P ) = ±1.Block matrix. A matrix can be partitioned into matrix blocks, by cuts between rowsand/or between columns. Block multiplication of AB is allowed if the block shapespermit (the columns of A and rows of B must be in matching blocks).Cayley-Hamilton Theorem. p(λ) = det(A − λI) has p(A) = zero matrix.Change of basis matrix M. The old basis vectors vjare combinationsPmijwiof the newbasis vectors. The coordinates of c1v1+···+ cnvn= d1w1+···+ dnwnare relatedby d = Mc. (For n = 2 set v1= m11w1+ m21w2, v2= m12w1+ m22w2.)Characteristic equation det(A − λI) = 0. The n roots are the eigenvalues of A.Cholesky factorization A = CCT= (L√D)(L√D)Tfor positive definite A.Circulant matrix C. Constant diagonals wrap around as in cyclic shift S. Every circulantis c0I + c1S + ··· + cn−1Sn−1. Cx = convolution c ∗ x . Eigenvectors in F .Cofactor Cij. Remove row i and column j; multiply the determinant by (−1)i+j.Column picture of Ax = b. The vector b becomes a combination of the columns of A.The system is solvable only when b is in the column space C (A).Column space C (A) = space of all combinations of the columns of A.Commuting matrices AB = BA. If diagonalizable, they share n eigenvectors.Companion matrix. Put c1, . . . , cnin row n and put n − 1 1’s along diagonal 1. Thendet(A − λI) = ±(c1+ c2λ + c3λ2+ ···).Complete solution x = xp+ xnto Ax = b. (Particular xp) + (xnin nullspace).Complex conjugate z = a − ib for any complex number z = a + ib. Then zz = |z|2.12 GlossaryCondition number cond(A) = κ(A) = kAkkA−1k = σmax/σmin. In Ax = b, the rela-tive change kδx k/kx k is less than cond(A) times the relative change kδbk/kbk.Condition numbers measure the sensitivity of the output to change in the input.Conjugate Gradient Method. A sequence of steps (end of Chapter 9) to solve positivedefinite Ax = b by minimizing12xTAx − xTb over growing Krylov subspaces.Covariance matrix Σ. When random variables xihave mean = average value = 0, theircovariances Σijare the averages of xixj. With means xi, the matrix Σ = mean of(x −x )(x −x )Tis positive (semi)definite; it is diagonal if the xiare independent.Cramer’s Rule for Ax = b. Bjhas b replacing column j of A, and xj= |Bj|/|A|.Crossproduct u ×v in R3. Vector perpendicular to u and v, length kukkvk|sin θ| = par-allelogram area, computed as the “determinant” of [ i j k ; u1u2u3; v1v2v3].Cyclic shift S. Permutation with s21= 1, s32= 1, . . ., finally s1n= 1. Its eigenvalues arenth roots e2πik/nof 1; eigenvectors are columns of the Fourier matrix F .Determinant |A| = det(A). Defined by det I = 1, sign reversal for row exchange, andlinearity in each row. Then |A| = 0 when A is singular. Also |AB| = |A||B| and|A−1| = 1/|A| and |AT| = |A|. The big formula for det(A) has a sum of n! terms,the cofactor formula uses determinants of size n − 1, volume of box = |det(A)|.Diagonal matrix D. dij= 0 if i 6= j. Block-diagonal: zero outside square blocks Dii.Diagonalizable matrix A. Must have n independent eigenvectors (in the columns of S;automatic with n different eigenvalues). Then S−1AS = Λ = eigenvalue matrix.Diagonalization Λ = S−1AS. Λ = eigenvalue matrix and S = eigenvector matrix. A musthave n independent eigenvectors to make S invertible. All Ak= SΛkS−1.Dimension of vector space dim(V ) = number of vectors in any basis for V .Distributive Law A(B + C) = AB + AC. Add then multiply, or multiply then add.Dot product xTy = x1y1+ ··· + xnyn. Complex dot product is xTy. Perpendicularvectors have zero dot product. (AB)ij= (row i of A)·(column j of B).Echelon matrix U. The first nonzero entry (the pivot) in each row comes after the pivotin the previous row. All zero rows come last.Eigenvalue λ and eigenvector x . Ax = λx with x 6= 0 so det(A − λI) = 0.Eigshow. Graphical 2 by 2 eigenvalues and singular values (MATLAB or Java).Elimination. A sequence of row operations that reduces A to an upper triangular Uor to the reduced form R = rref(A). Then A = LU with multipliers `ijin L, orP A = LU with row exchanges in P , or EA = R with an invertible E.Elimination matrix = Elementary matrix Eij. The identity matrix with an extra −`ijin thei, j entry (i 6= j). Then EijA subtracts `ijtimes row j of A from row i.Ellipse (or ellipsoid) xTAx = 1. A must be positive definite; the axes of the ellipse areeigenvectors of A, with lengths 1/√λ. (For kx k = 1 the vectors y = Ax lie on theellipse kA−1yk2= yT(AAT)−1y = 1 displayed by eigshow; axis lengths σi.)Exponential eAt= I + At + (At)2/2! + ··· has derivative AeAt; eAtu(0) solves u0= Au.Glossary 3Factorization A = L U. If elimination takes A to U without row exchanges, then thelower triangular L with multipliers `ij(and `ii= 1) brings U back to A.Fast Fourier Transform (FFT). A factorization of the Fourier matrix Fninto ` = log2nmatrices Sitimes a permutation. Each Sineeds only n/2 multiplications, so Fnxand F−1nc can be computed with n`/2 multiplications. Revolutionary.Fibonacci numbers 0, 1, 1, 2, 3, 5, . . . satisfy Fn= Fn−1+ Fn−2= (λn1− λn2)/(λ1− λ2).Growth rate λ1= (1 +√5)/2 is the largest eigenvalue of the Fibonacci matrix1 11 0 .Four fundamental subspaces of A = C (A), N (A), C (AT), N (AT).Fourier matrix F . Entries Fjk= e2πijk/ngive orthogonal columns FTF = nI. Theny = F c is the (inverse) Discrete Fourier Transform yj=Pcke2πijk/n.Free columns of A. Columns without pivots; combinations of earlier columns.Free variable xi. Column i has no pivot in elimination. We can give the n − r freevariables any values, then Ax = b
View Full Document
Unlocking...