0
$\begingroup$

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} $$
|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Ben McKay Jun 9 '18 at 14:17
  • 1
    $\begingroup$ Yes, it is. I will make some modification $\endgroup$ – mortal Jun 13 '18 at 13:20
  • 2
    $\begingroup$ 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. $\endgroup$ – Dirk Jun 13 '18 at 19:25
  • 1
    $\begingroup$ Looks like it's still easy to find the eigenvalues of that one... By the way, is $\mathbb{I}_{mn}$ the identity matrix? $\endgroup$ – Federico Poloni Jun 14 '18 at 12:10
  • 1
    $\begingroup$ So your matrix in case 1 is block diagonal with blocks like here math.stackexchange.com/questions/755113/… - so the eigenvalues are known explicitly. $\endgroup$ – Dirk Jun 18 '18 at 15:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.