Practice Session

Consider a matrix $A_n$ of size $n\times n$ $$ A_n = \begin{pmatrix} 2 & -1 & 0 & 0 & \dots & 0 & -1 \\ -1 & 2 & -1 & 0 & \dots & 0 & 0 \\ 0 & -1 & 2 & -1 & \dots & 0 & 0 \\ \dots & \dots & \dots& \dots& \dots& \dots & \dots\\ \dots & \dots & \dots& \dots& \dots& \dots & \dots\\ 0 & 0 & \dots & \dots & -1 & 2 & -1 \\ -1 & 0 & \dots & \dots & 0 & -1 & 2 \end{pmatrix} $$

Properties

  • Symmetric: $A^T = A$
  • Hermitian: $A^* = A$ (hence real eigenvalues)
  • Singular (take sum of all rows)
  • Non-negative definite: $(Ax, x) \geq 0$ for each $x\in\mathbb{C}^{n\times 1}$
  • Sparse: $\mathcal{O}(n)$ non-zero elements
  • Toeplitz
  • Circulant
  • Discretization of an operator $A$ on unifrom grid: $$ \begin{split} Au \equiv &\frac{d^2 u(x)}{dx^2}, \quad x\in (0,1)\\ u(0) &= u(1) \\ u'(0) &= u'(1) \end{split} $$

Eigenvalues

As we know circulants have eigenvalues equal to the multiplication of the Fourier matrix by circulant's first column: $$ \begin{pmatrix} \lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \vdots \\ \lambda_n \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & \dots & 1 \\ 1 & w^{1\cdot 1}_n & w^{1\cdot 2}_n & \dots & w^{1\cdot (n-1)}_n\\ 1 & w^{2\cdot 1}_n & w^{2\cdot 2}_n & \dots & w^{2\cdot (n-1)}_n\\ \dots & \dots & \dots &\dots &\dots \\ 1 & w^{(n-1)\cdot 1}_n & w^{(n-1)\cdot 2}_n & \dots & w^{(n-1)\cdot (n-1)}_n\\ \end{pmatrix} \begin{pmatrix} 2 \\ -1 \\ 0 \\ \vdots \\0 \\ -1 \end{pmatrix} = \begin{pmatrix} 2 -1 -1 \\ 2 - w_n^{1} - w_n^{n-1} \\ 2 - w_n^{2} - w_n^{2(n-1)} \\ \vdots \\ 2 - w_n^{(n-1)} - w_n^{(n-1)(n-1)} \end{pmatrix} $$ Thus, $$ \lambda_k = 2 - w_n^k - w_n^{k(n-1)} = 2 - w_n^k - w_n^{-k} = 2 - e^{-\frac{2\pi i}{n}k} - e^{\frac{2\pi i}{n}k} = 2 - 2 \cos \frac{2\pi k}{n} = 4 \sin^2 \frac{\pi k}{n}, $$ So, $$\lambda_k = 4 \sin^2 \frac{\pi k}{n} \geq 0, \quad k=0,1,\dots, n-1$$ Therefore, our matrix is non-negative definite. Note that $\lambda_0 = 0$, hence matrix is singular.

Norms

$$ \begin{split} \|A_n\|_F &= \left((-1)^2 (n-1) + (-1)^2 (n-1) + 2^2 n + (-1)^2 + (-1)^2\right)^{1/2} = \sqrt{6n} \\ \|A_n\|_1 &= \lvert -1\lvert + \lvert 2\lvert + \lvert -1\lvert = 4 \\ \|A_n\|_\infty &= \lvert -1\lvert + \lvert 2\lvert + \lvert -1\lvert = 4 \\ \|A_n\|_2 &= \max_i |\lambda_i| = \begin{cases} 4 \sin^2 \frac{\pi n/2}{n} = 4, & \text{if } n \text{ is even } \\ 4 \sin^2 \frac{\pi ({n-1})/2}{n}, & \text{if } n \text{ is odd } \end{cases} \\ \end{split} $$

Note, that $\|A_n\|_2 = \max_i |\lambda_i|$ only for Hermitian matrices!