Eigenvalue and co

Eigenvalue (ew)

ew problem

Aka: ew or eigenwert. For square $A$ only. These are solutions to the eigenvalue problem: $Ax=\lambda x$ (Eigen = distinctive). This defines the Eigen pair: $(\lambda ,x)$, where $\lambda$ is ew, x is a (right) ev (eigen vector).

Left and right eigenpairs

Also, can define left ev and ew by the relation $xA=\lambda x$. ew of $A$ and left ew of $A^T$ are same.

ew of $A$ and ew of $A^T$ are the same if $A$ is real: By Schur, \(A=QUQ^{}\), \(A^{}=QU^{}Q^{}\). As \(QU^{}Q^{}\) is a similarity transformation, and $U^{\ast }$ is triangular, the ew of $A$ are still $diag(U)$.

In the case of diagonalizable A, ew decomposition $AS=S\mathrm{\Lambda }$ reveals that rows of $S^{-1}$ are the left ev: For details see ew decomposition section.

Characteristic polynomial

As $(A-\lambda I)x=0$, $det(A-\lambda I)=0$. 0 is always an ev.

Other things apart, this implies that ew of a triangular matrix are on its diagonal.

Mapping polynomials to matrices

Every polynomial $p(\lambda )={\lambda }^m+a_{m-1}{\lambda }^{m-1}..+a_0$ determinant of some matrix; Eg: $\left[\begin{array}{ccc}\lambda & a_0-1& \lambda +a_1\end{array}\right]$ for m=2; which is $A-\lambda I$ for some companion matrix A.

Applications

Domain and range of $A$ are the same space. Useful where iterative calculations: $A^k$ or $e^{tA}$ occur.

Physics: evolving systems generated by linear equations; Eg: resonance, stability.

Simpler algorithms: Reduces coupled system into a collection of scalar systems. \why

ew and ev properties

ew properties

For connection with matrices, distribution etc.. see later section.

Number of ew

There are n ew in $C$. Algebraic multiplicity of ew: number of times an ew appears as root of $p(\lambda )$.

0 as an ew

If $A$ full rank, 0 is not an ew: $Ax=\lambda x$ else A’s columns would be dependent. If 0 is an ew, $E_0=N(A)$.

Eigenspace of an ew

If x is an ev corresponding to $\lambda$, so is -x and kx for any scalar k. For every $\lambda$, ev span the null space of $A-\lambda I$.

An invariant subspace: $A{E}_{\lambda }\subseteq E_{\lambda }$. $E_{{\lambda }_1}=N(A-{\lambda }_{1}I)$.

Independence of ev

ev $x_1,x_2$ (non-0) for distinct ew ${\lambda }_1,{\lambda }_2$ are linearly independent: otherwise action of $A$ on collinear $x_1,x_2$ would involve the same scaling.

Defective matrices

Geometric multiplicity of $\lambda$ $\le$ algebraic multiplicity: Let n be geometric multiplicity of $\lambda$ in A; Select orth vectors in $E_{\lambda }$ to get $\hat{V}$; extend it to square V; take $B=V^{\ast }AV=\left[\begin{array}{ccc}\lambda I& C0& D\end{array}\right]$; but $det(B-zI)=det(\lambda I-zI)det(D-zI)=(\lambda -z{)}^{n}det(D-zI)$: so algebraic multiplicity of $\lambda$ in B $\ge n$, same in A.

If algebraic multiplicity of ew exceeds geometric multiplicity, ew is defective. If $A$ has defective ew, it is defective. Eg: Diagonal matrix never defective.

Rayleigh quotient of x

$r(x)=\frac{x^{T}Ax}{x^{T}x}$. Like solving the least squares problem: $xa\approx Ax$ for a; thereby approx eigenvalue. Range(r(x)): Field of values of numerical range of A: W(A). Includes Convex hull of $\mathrm{\Lambda }(A)$.

EV as stationary points

$\frac{\mathrm{\partial }r(x)}{\mathrm{\partial }{x}_j}=\frac{2(Ax-r(x)x{)}_j}{{\parallel x\parallel }^2}$; their vector, the gradient $\mathrm{\nabla }r(x)=\frac{2(Ax-r(x)x)}{{\parallel x\parallel }^2}$. ev are the stationary points: $\mathrm{\nabla }r(x)=0$ iff x is ev and r(x) is ew.

Geometry

$r(x):S^{n-1}\to R$. Normalized ev of $A$ are stationary points of r(x) for $x\in S^{n-1}$.

maxmin thm for symmetric A

[Courant Fishcer]. ${\lambda }_i$ descending. Then ${\lambda }_i=\underset{S:dim(S)=i}{max}\underset{y\ne 0\in S}{min}{R}_A(y)$.

Quadratic Accuracy of ew wrt ev error

For $A=A^T$, let $q_i$ be ev. Then, any $x=\sum _i{a}_i{q}_i$, $r(x)=\frac{\sum a_i^2{\lambda }_i}{\sum a_i^2}$. So, W(A) = Convex hull of $\mathrm{\Lambda }(A)$. So, $ma{x}_{x}r(x)={\lambda }_{max}$. Also, $r(x)-r(q_i)=O({\parallel x-q_i\parallel }^2)$ as $x\to q_i$ or $\mathrm{\forall }j:|a_j/a_i|\le ϵ$.

Rayleigh quotient of M: Generalization

If $A$ = mm, M is mn: thin, tall, required to be full rank.\ $r(M)=tr((M^{T}M{)}^{-1}(M^{T}AM))$.

Take svd: $M=U\mathrm{\Sigma }{V}^{\ast }$. Then \ $maxr(M)=\underset{U}{max}|tr(U^{T}AU)|=\underset{U}{max}\prod |R(u_i)|$. This happens when U is top k unique ev(A).

ew and matrices: other connections

ew distribution

Set of ew: Spectrum of A: $\mathrm{\Lambda }(A)$. Spectral radius: $\rho (A)=|{\lambda }_{max}|$. ew follows wigner’s semicircle distribution for random matrices. \why

ew and the diagonal

In Disks around the diagonal

(Gerschgorin) In complex plane, take disks with center $A_{i,i}$, radii $\sum _{j\ne i}{A}_{i,j}$; each ew lies in atleast one disk: Take ev v and ew l; take $i=argma{x}_i{v}_i$; then $|\lambda -a_{i,i}|\le |\sum _{j\ne i}{a}_{i,j}\frac{v_j}{v_i}|\le |\sum _{j\ne i}{a}_{i,j}|$. Good estimate of ew!

Monotonic dependence on diagonal

Take \(A = QTQ^{}\), take any +ve diagonal D; get \(A+D = Q(T+D)Q^{}\). Used to take $A\notin S_{+}toB\in S_{+}$.

Effect of transformations

Similarity transformation

X nonsingular, square; $A\to B=X^{-1}AX$. $A$, B similar if $\mathrm{\exists }X:B=X^{-1}AX$.

Change of basis op: See Ax=b as $AX{x}^{\prime }=X{b}^{\prime }$ when $X{x}^{\prime }=x$, $X{b}^{\prime }=b$, so $B{x}^{\prime }=b^{\prime }$.

$p_{X^{-1}AX}=det(\lambda I-X^{-1}AX)=det(X^{-1}(\lambda I-A)X)=det(\lambda I-A)=p_A$. So, ew’s, their agebraic multiplicities same. Geometric multiplicities same: $X^{-1}{E}_{\lambda }$ is eigenspace of $X^{-1}AX$: if $Ax=\lambda x$, $B{X}^{-1}x=\lambda X^{-1}x$.

Eigenpairs of \htext{\(A^{k\)}{..}}

\(A^{k} = (QUQ^{})^{k} = QU^{k}Q^{}\). So, ew are ${\lambda }_i^k$. So, ew of $A^{-1}$ are $\frac{1}{{\lambda }_i}$: $L^{-1}=(S^{-1}AS{)}^{-1}=S^{-1}{A}^{-1}S$.

Matrix construction

Matrix with certian ew and diagonal entries

If real $\lambda$ majorizes $A$, $\mathrm{\exists }$ real symmetric $A$ with $a_{i,i}=a_{(i)}$, such that ${\lambda }_{(i)}$ are ew of A. Pf: By induction; assume true for n-1; Take $g\in R^{n-1}$ interleaved amongst $\lambda$ which majorizes a; by ind hyp, take real symmetric $B=QG{Q}^{\ast }$ with diagonal a and ew g; can make $A^{\prime }=\left[\begin{array}{ccc}G& y{y}^T& \alpha \end{array}\right]$ with ew $\lambda$; take $A=\left[\begin{array}{ccc}Q& 00& 1\end{array}\right]A^{\prime }\left[\begin{array}{ccc}{Q}^T& 00& 1\end{array}\right]=\left[\begin{array}{ccc}B& Qy{y}^T{Q}^T& \alpha \end{array}\right]$ with ew $\lambda$ and diag a.

Extending \htext{$\mathrm{\Lambda }${EW} to A with certain interleaving \htext{$\lambda (A)$}{ew}}

Take $\lambda \in R^n$ interleaved between $l\in R^{n+1}$. Can make real $A=\left[\begin{array}{ccc}\mathrm{\Lambda }& y{y}^T& a\end{array}\right]$ with $\lambda (A)=l$.

Pf where ${\lambda }_i$ differ: $a=tr(A)-tr(\mathrm{\Lambda })=\sum l_i-\sum {\lambda }_i$. Take $det(tI-A)=det[\left[\begin{array}{ccc}I& (tI-\mathrm{\Lambda }{)}^{-1}y{0}^T& 1\end{array}\right]\left[\begin{array}{ccc}tI-\mathrm{\Lambda }& -y-y^T& t-a\end{array}\right]\left[\begin{array}{ccc}\mathrm{\Lambda }& y{y}^T& a\end{array}\right]]$ (multiplicity two matrices with det = 1) $=[(t-a)-y^T(tI-\mathrm{\Lambda }{)}^{-1}y]det(tI-\mathrm{\Lambda })=(t-a)-\sum _i{y}_i^2(t-{\lambda }_i{)}^{-1}\prod _i(t-{\lambda }_i)=p_A(t)$.

Find y to make $p_A(l_i)=0$. Characterize y, show it exists: Take $f(t)=\prod (t-l_i),g(t)=\prod (t-{\lambda }_i)$, so $f(t)=g(t)(t-c)+r(t)$, where r(t) has degree $\le n-1$. $c=\sum _i{l}_i-\sum _i{\lambda }_i=a$; $f({\lambda }_i)=r({\lambda }_i)$, so get Lagrange interpolation form of $r(t)=\sum _{i}f({\lambda }_i)\frac{g(t)}{g^{\prime }({\lambda }_i)(t-{\lambda }_i)}$. So, $\frac{f(t)}{g(t)}=(t-a)-\sum _i\frac{-f({\lambda }_i)}{g^{\prime }({\lambda }_i)(t-{\lambda }_i)}$; this is $0\mathrm{\forall }t=l_i$ and $y_i^2=\frac{-f({\lambda }_i)}{g^{\prime }({\lambda }_i)}$. But, by interlacing, $f({\lambda }_i)=(-1{)}^{n-i+1}\prod _j|{\lambda }_i-l_j|$ and $g^{\prime }({\lambda }_i)=(-1{)}^{n-i}\prod _{j\ne i}|{\lambda }_i-{\lambda }_j|$ oppose in sign, so $\mathrm{\exists }y$.

Pf where $e{w}_i$ recurs: Divide out $(t-{\lambda }_i{)}^k$ from all, proceed as usual.

EW of special matrices

Real A: complex ew in pairs

If $A$ is real, $p_A$ has real coefficients.

So, if l is ew of $A$, so is $\overline{\lambda }$: complex roots of P appear in pairs. ew simple if its algebraic multiplicity 1.

Triangular and diagonal A

For triangular $A$, from $det(A-\lambda I)=0$, ew are on diagonal. So, $tr(A)=\sum A_{i,i}=\sum {\lambda }_i$. Also, $\prod {\lambda }_i=|A|$. For diagonal $A$, eigenpairs are diagonal element $(A_{i,i},k{e}_i)$.

Nilpotent matrix A

A is a nilpotent op (see algebra ref). So, all ew are 0; $|A|$, tr(A) are 0. Any singular $A$ = product of nilpotent matrices.

Singular A

0 is an ew.

Semidefiniteness and hermitianness

See other sections.

Generalized eigenvalue problem

$Az=\lambda Bz$. $det(A-\lambda B)=0$. $\{A-\lambda B\}$ is called pencil.

General Rayleigh quotient of x

\(R(x) = \frac{x^{}Ax}{x^{}Bx}\). $\mathrm{\nabla }R(x)=2(Ax-R(x)Bx)$ is 0 exactly where R(x) is $\lambda$, x the ev.

Of M

M is tall, thin, with independent columns. \ \(R(M) = tr((M^{}BM)^{-1} (M^{}AM))\). Using svd \(M = U\SW V^{}\):\ get \(R(M) = tr_{U}(U^{}B^{-1}AU)\): same as common rayleigh quotient of $B^{-1}A$: see ev section. Maximized when U is the top ev’s of $B^{-1}A$.

Reductions to common ew problem

If B is invertible: $B^{-1}Az=\lambda z$: so now an $\lambda$ problem. Don’t want to invert: so solve some other way.

So, if B is invertible, symmetric, +ve definite: \(R(x) = \frac{x^{}Ax}{x^{}B^{1/2}B^{1/2}x}\); taking $z=B^{1/2}x$, get \(R(z) = \frac{z^{}B^{-1/2}AB^{-1/2}z}{z^{}z}\). Max of R(x) is achieved somewhere in R(z) as $z\to x$ is a 1 to 1 map. ew of $B^{-1/2}A{B}^{-1/2}$ are easier to find as it is symmetric.

Matrix to matrix functions

\htext{\((I-A)^{-1\)}{Neumann} series for square A}

Aka Neumann series. $(I-A{)}^{-1}=\sum _{k=0}^{\mathrm{\infty }}{A}^k$, if it converges. It converges when $A$ has norm $<1$.

Matrix exponentiation for square A

$e^A=\sum _{k=0}^{\mathrm{\infty }}\frac{A^k}{k!}$: always converges. Also defines $\log A$. If $A$ nilpotent, series is finite.

Using expansion, aggregating suitably: $e^{aX}{e}^{bX}=e^{(a+b)X}$; If $XY=YX:e^X{e}^Y=e^{X+Y}$.

$e^X{e}^{-X}=I$: So exponential of X is always invertible.

$e^{YX{Y}^{-1}}=Y{e}^X{Y}^{-1}$.

\(e^{X^{}} = (e^{X})^{}\).

If D diagonal, easy to get $e^D$. Thence easily get $e^A$ if $A=XD{X}^{-1}$ (A diagonalizable).

Relationship among ew

As $e^{\lambda (A)}=\lambda (e^A),det(e^A)=e^{\sum {\lambda }_i(A)}=e^{tr(A)}$.