Term

Definition
Ax = λx. The matrix expands or shrinks any vector lying in the direction of x by a scalar multiple (the eigenvalue). 


Term

Definition
Ax = λx. Any vector in a given direction that is shrunk or expanded by a scalar multiple when multiplied by A. 


Term
Characteristic Polynomial 

Definition
(AλI)x = 0 has a nonzero solution only if the matrix is singular. So det(AλI) must equal 0, where det(AλI) is a polynomial of degree n. Roots = eigenvalues of A. 


Term

Definition
An nxn matrix satisfies its own characteristic equation, that is, if
p(λ) = c_{0} + c_{1}λ + ... + c_{n1}λ^{n1} + λ^{n} = 0
then
p(A) = c_{0} + c_{1}A + ... + c_{n1}A^{n1} + A^{n} = 0 


Term
Algebraic and Geometric Multiplicity 

Definition
Algebraic multiplicity is the number of times a given eigenvalue appears. The multiplicity as a root of the characteristic polynomial.
Geometric multiplicity is the number of linearly independent eigenvectors corresponding to the eigenvalue. 


Term

Definition
If geometric multiplicity is less than algebraic multiplicity, the nxn matrix has fewer than n linearly independent eigenvectors and it is said to be defective. This means it is not diagonalizable 


Term

Definition
Any nondefective matrix has a full set of linearly independent eigenvectors, let D be a diagonal matrix of eigenvalues and X be a matrix of eigenvectors. X is nonsingular. AX = DX can be rewritten as X^{1}AX = D, so A is diagonalizable. 


Term

Definition


Term

Definition
For a given matrix A, a given subspace S of R^{n} is said to be an invariant supspace if AS is a subset of S.
i.e. if x in S implies Ax in S. 


Term

Definition
Every matrix can be transformed into triangular form (Schur form) by a similarity transformation. 


Term

Definition
A block triangular matrix with only real entries, having 1x1 or 2x2 diagonal blocks corresponding to real eigenvalues and complex conjugate pairs of eigenvalues respectively. 


Term

Definition
The closest any general matrix can come to diagonal form. The matrix is reduced to nearly diagonal form, but may yet have a few nonzero entries in the first superdiagonal corresponding to one or more multiple eigenvalues. Cannot be computed stably. 


Term

Definition
The eigenvalues of an nxn matrix A are all contained within the union of n disks, with the kth disk centered at a_{kk} and having radius ∑_{j≠k}a_{kj}. 


Term
Problem Transformations: Shift 

Definition
Subtracts a constant scalar from each diagonal entry of a matrix, shifting the origin of the real line or complex plane.
(AσI)x=(λσ)x. 


Term
Problem Transformation: Inversion 

Definition
If A is nonsingular, and Ax = λx for nonzero x, then λ is nonzero so
A^{1}x=(1/λ)x. 


Term
Problem Transformation: Powers 

Definition
If Ax = λx, then A^{2}x = λ^{2}x. Taking the kth power of a matrix also takes the kth power of the eigenvalues without changing the eigenvectors 


Term
Problem Transformations: Polynomials 

Definition
If p(t) = c_{0} + c_{1}t + c_{2}t^{2} + ... + c_{k}t^{k} then
p(A) = c_{0} + c_{1}A + c_{2}A^{2} + ... + c_{k}A^{k.}
If Ax = λx then p(A)x = p(λ)x. 


Term
Problem Transformations: Similarity 

Definition
A matrix B is similar to a matrix A if there is a nonsingular matrix T such that B = T^{1}AT.
By = λy
T^{1}ATy = λy
ATy = λTy
x = Ty 


Term

Definition
x = arbitrary nonzero vector
for k = 1, 2, ...
y_{k}= Ax_{k1}
x_{k} = y_{k}/y_{k}_{∞}



Term

Definition
x_{0}=arbitrary nonzero vector
for k = 1, 2, ...
Solve Ay_{k}=x_{k1} for y_{k}
x_{k}=y_{k}/y_{k}_{∞} 


Term
Raleigh Quotient Iteration 

Definition
x_{0}=arbitrary nonzero vector
for k = 1, 2, ...
σ_{k} = x_{k1}TAx_{k1}/x_{k1}^{T}x_{k1}
Solve (A  σ_{k}I)y_{k} = x_{k1}
x_{k}=y_{k}/y_{k}_{∞} 


Term

Definition
Let H be any nonsingular matrix (Householder is a good one) such that Hx_{1}=αe_{1}. Similarity transformation gives
[image]



Term

Definition
X_{0} = arbitrary nxp matrix of rank p
for k = 1,2, ...
X_{k} = AX_{k1} 


Term

Definition
X_{0} = arbitrary nxp matrix of rank p
for k = 1, 2, ...
compute reduced QR factorization
Q_{k}R_{k}=X_{k1}
X_{k}=AQ_{k} 


Term

Definition
A_{0}=A
for k = 1, 2, ...
compute QR factorization
Q_{k}R_{k}=A_{k1}
A_{k}=R_{k}Q_{k} 


Term

Definition
A_{0}=A
for k = 1, 2, ...
Choose shift σ_{k}
Compute QR Factorization
Q_{k}R_{k}=A_{k1}σ_{k}I
A_{k}=R_{k}Q_{k}+σ_{k}I 


Term

Definition
Build up a subspace incrementally, one vector at a time. Let A be an nxn matrix, x0 an arbitrary starting vector, and for k>0, define the Krylov sequence x_{k}=Ax_{k1}
Krylov Matrix  K_{k} = [x_{0} x_{1} ... x_{k1}]
Krylov subspace span(K_{k}) 


Term

Definition
Krylov subspace method... Each iteration you generate the next vector u = Au. Then orthogonalize against all previous and normalize. 


Term

Definition
For symmetric (or Hermitian) matrices, H is tridiagonal rather than just Hessenberg. Three term recurrence. 


Term

Definition
Plane Rotations (like Givens)
A_{0}=A (real symmetric matrix)
A_{k+1}=J_{k}^{T}A_{k}J_{k}
where J is a plane rotation chosen to annihilate a symmetric pair of entries 

