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.
- $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} . $$
- $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} $$