More Matrices

Eigenvalue/ Eigenvector

• $A$: an
  $n\times n$ matrix,
  $v$: a vector
  $\in {\mathbb{R}}^n$,
  $\lambda :$ a scalar
• If there exist a nonzero vector
  $v$ such that
  $Av=\lambda v$, we say
  $v$ is an eigenvector and
  $\lambda$ is the eigenvalue for
  $v$
• Fact: eigenvectors corresponding to distinct eigenvalues are linearly independent

Matrix Diagonalization

• Fact: not all matrices are diagonalizable
• If an
  $n\times n$ matrix
  $A$ is diagonalizable, it can be decomposed as
  • $A=PD{P}^{-1}$
    • $D$ is a diagonal matrix with
      ${\lambda }_1\cdots {\lambda }_n$ diagonal entries
    • $P=[p_1\cdots p_n]$ is an invertible matrix
  • $AP=PD$
    • $AP=[A{p}_1\cdots A{p}_n]$
    • $PD=[{\lambda }_1{p}_1\cdots {\lambda }_n{p}_n]$
  • $A{p}_i={\lambda }_i{p}_i$. Thus,
    $p_i$ is an eigenvector of
    $A$ with eigenvalue
    ${\lambda }_i$
  • Because
    $P$ is invertible, the column vectors of
    $P$ (the eigenvectors of
    $A$) are independent
  • $A^n=P{D}^n{P}^{-1}$ (computationally efficient!)

Symmetric Matrix

• definition:
  $A=A^{\mathrm{\top }}$
• Fact: symetric matrix is diagonalizable, and its eigenvectors can be chosen to form an orthonormal basis of
  ${\mathbb{R}}^n$
• $A=UD{U}^{-1}$ (diagonalization)
  • $U$ is an orthogonal matrix
    • its column vectors are orthonormal
    • $U^{\mathrm{\top }}U=I=U{U}^{\mathrm{\top }}$
    • $U^{-1}=U^{\mathrm{\top }}$
  • $A=UD{U}^{\mathrm{\top }}$
• Quadratic form:
  $x^{\mathrm{\top }}Ax$
  • $A$ is a symmetric matrix,
    $x$ is a vector
  • $x^{\mathrm{\top }}Ax=x^{\mathrm{\top }}UD{U}^{\mathrm{\top }}x$
  • Let
    $y=U^{\mathrm{\top }}x$,
    
    $x^{\mathrm{\top }}Ax=(x^{\mathrm{\top }}U)D(U^{\mathrm{\top }}x)=y^{\mathrm{\top }}Dy={\mathrm{\Sigma }}_i{\lambda }_i{y}_i^2\le {\lambda }_{\text{max}}{\mathrm{\Sigma }}_i{y}_i^2={\lambda }_{\text{max}}{y}^{\mathrm{\top }}y={\lambda }_{\text{max}}{x}^{\mathrm{\top }}x$
    • proof.
      $y^{\mathrm{\top }}y=(U^{\mathrm{\top }}x{)}^{\mathrm{\top }}(U^{\mathrm{\top }}x)=x^{\mathrm{\top }}U{U}^{\mathrm{\top }}x=x^{\mathrm{\top }}U{U}^{-1}x=x^{\mathrm{\top }}x$ (orthogonal maxtrix preserves norm)
    • ${\lambda }_{\text{max}}$ (resp.
      ${\lambda }_{\text{min}}$): the largest (resp. smallest) eigenvalues among all eigenvalues of
      $A$
  • ${\lambda }_{\text{min}}{x}^{\mathrm{\top }}x\le x^{\mathrm{\top }}Ax\le {\lambda }_{\text{max}}{x}^{\mathrm{\top }}x$