Maximum Eigenvalue of the Discrete Laplace Operator (Image Processing)

Question

Given the derivative operator in image processing

$$ A = \begin{bmatrix} 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 1 & -1 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & \ldots & 0 & 0 \\ 0 & 0 & 0 & 1 & -1 & 0 & \ldots & 0 \\ & & & \vdots & & & & \end{bmatrix} $$

The Laplacian (Discrete Laplace Operator) would be given by

$$ A {A}^{T} $$

I read its maximum eigenvalue is bounded by $ 4 $.
How can it be shown?

Answer 1

The form of $ A {A}^{T} $ is given by

$$ B = A {A}^{T} = \begin{bmatrix} 2 & -1 & 0 & \ldots & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 & \ldots & 0 & 0 \\ 0 & -1 & 2 & -1 & 0 & \ldots & 0 \\ & & & \vdots & & & \end{bmatrix} $$

Using Gershgorin Disc Theorem the discs are given by $ {R}_{ii} = \sum_{j \neq = i} \left| {b}_{ij} \right| \leq 2 $ and $ {b}_{ii} = 2 $ hence $ \forall i \; {\lambda}_{i} \leq 4 $

Answer 2

Hint. Simply calculate $AA^T$ explicitly and apply Gershgorin disc theorem.

Answer 3

$\mathrm A$ is an $(n-1) \times n$ incidence matrix. $\mathrm A \mathrm A^T$ is a Toeplitz and tridiagonal $(n-1) \times (n-1)$ symmetric matrix with $2$'s on its main diagonal and $-1$'s in the subdiagonal and superdiagonal. Hence, the $n-1$ real eigenvalues of $\mathrm A \mathrm A^T$ are given by [0]

$$\lambda_k (\mathrm A \mathrm A^T) = 2 + 2 \cos \left(\frac{k \pi}{n}\right)$$

for $k \in \{1,2,\dots,n-1\}$. Thus,

$$0 < 2 - 2 \cos \left(\frac{\pi}{n}\right) \leq \lambda_k (\mathrm A \mathrm A^T) \leq 2 + 2 \cos \left(\frac{\pi}{n}\right) < 4$$

---

[0] Silvia Noschese, Lionello Pasquini, and Lothar Reichel, Tridiagonal Toeplitz Matrices: Properties and Novel Applications, 2006.