# Smallest eigenvalue of a sparse matrix (updated)

Let $D_{1}$ be $(m-1)n \times mn$ matrix (that is, $(m-1)n$ rows and $mn$ columns) and $D_{2}$ be $m(n-1) \times mn$ defined as $$\begin{cases} D_{1}[(m-1)(j-1)+i ; m(j-1)+i] & = -1 , \\ D_{1}[(m-1)(j-1)+i ; m(j-1)+i+1] & = 1 , \end{cases} , \quad \forall 1 \leq i \leq m-1, \forall 1 \leq j \leq n ,$$ and $$\begin{cases} D_{2}[m(j-1)+i ; m(j-1)+i] & = -1 , \\ D_{2}[m(j-1)+i ; mj+i] & = 1 , \end{cases} , \quad \forall 1 \leq i \leq m, \forall 1 \leq j \leq n-1 .$$

The main goal is to find the smallest eigenvalue of $DD^{T}$, $\lambda_{\min} \left( DD^{T} \right)$, where $$D = \begin{pmatrix} D_{1} & \\ & D_{2} \\ \mathbb{I}_{mn} & \mathbb{I}_{mn} \end{pmatrix}.$$

Notation: $D_{k} \left[ r , c \right]$ means the element of $D_{k}$ at row $r$ and column $c$.

## Example

When $m=2$ and $n=3$, we have $$D_{1} = \begin{pmatrix} -1 & 1 \\ & & -1 & 1 \\ & & & & -1 & 1 \end{pmatrix}$$ and $$D_{2} = \begin{pmatrix} -1 & & 1 \\ & -1 & & 1 \\ & & -1 & & 1 \\ & & & -1 & & 1 \end{pmatrix}.$$

Since $m$ and $n$ are quite large, I wonder if we can find an exact formula of $\lambda_{\min} \left( DD^{T} \right)$ instead of relying on iterative method. Otherwise, having explicit formula for $\lambda_{\min} \left( D_{1}D_{1}^{T} \right)$ and $\lambda_{\min} \left( D_{2}D_{2}^{T} \right)$ would also be really nice.

## UPDATE

I derived the exact formula of $D_{1}D_{1}^{T}$ and $D_{2}D_{2}^{T}$ when $m,n > 2$. Hope that it would be helpful.

1. $D_{1}D_{1}^{T}$ is a $(m-1)n \times (m-1)n$ matrix contains $n$-blocks in the main diagonal $$D_{1}D_{1}^{T} = \begin{pmatrix} B \\ & B \\ & & \ddots \\ & & & B \end{pmatrix}$$ where $B$ is a $(m-1) \times (m-1)$ matrix defined as $$B = \begin{pmatrix} 2 & -1 \\ -1 & 2 & -1 \\ & \ddots & \ddots & \ddots \\ & & -1 & 2 & -1 \\ & & & -1 & 2 \end{pmatrix} .$$
2. $D_{2}D_{2}^{T}$ is a $m(n-1) \times m(n-1)$ matrix with $m$ diag contains $2$ in the main diagonal and $-1$ at the $m^{th}$-upper and lower diagonal $$D_{2}D_{2}^{T} \left[ r , c \right] = \begin{cases} 2 & \textrm{ if } r = c , \\ -1 & \textrm{ if } \left\lvert r-c \right\rvert = m , \\ 0 & \textrm{ otherwise } . \end{cases}$$
• Are you using the notation $A[i;j]$ to mean $A_{ij}$? Could you make the definitions of $D_1$ and D_2$clearer, please? – Ben McKay Jun 9 '18 at 14:17 • Yes, it is. I will make some modification – mortal Jun 13 '18 at 13:20 • It would help, if you could indicate the range of$i$and$j$in the definitions of$D_1$and$D_2$. It is still unclear. In your small example$D_1D_1^T$is just$2I$, btw. – Dirk Jun 13 '18 at 19:25 • Looks like it's still easy to find the eigenvalues of that one... By the way, is$\mathbb{I}_{mn}\$ the identity matrix? – Federico Poloni Jun 14 '18 at 12:10
• So your matrix in case 1 is block diagonal with blocks like here math.stackexchange.com/questions/755113/… - so the eigenvalues are known explicitly. – Dirk Jun 18 '18 at 15:31