I have a Laplacian matrix ($L$), which is positive semi-definit. Then I have this matrix

$$\Delta=\begin{bmatrix} \delta_{11} & \ldots & \delta_{1n} \\ \vdots & \ddots & \vdots \\ \delta_{n1} & \ldots & \delta_{nn} \end{bmatrix}$$ in which $\delta_{ij}=e_ie_{j}^{T}$, and $e_i$ is a vector.

I need to form the following matrix, and analyze the eigenvalues.

$$\begin{bmatrix} l_{11}\delta_{11} & \ldots & l_{1n}\delta_{1n} \\ \vdots & \ddots & \vdots \\ l_{n1}\delta_{n1} & \ldots & l_{nn}\delta_{nn} \end{bmatrix}$$ where $l_{ij}$ is a scalar, but $\delta_{ij}$ is a matrix. This certainly looks like the Hadamard product, but the problem is that the dimensions of $L$ and $\Delta$ don't necessarily match.

Any ideas about the eigenvalues?

  • $\begingroup$ Is each $\delta_{ij}$ of size $n\times n$? And is your $L$ the matrix with elements $\ell_{ij}$ (thus also of size $n\times n$) ? And the $e_i$'s are any vectors? $\endgroup$ – H. H. Rugh Aug 6 '16 at 13:10
  • $\begingroup$ @H.H.Rugh thanks for your comment. The size of each $\delta_{ij}$ will differ according to the size of vector $e_i$. For example, consider $e_1=[1, 0]^T$ and $e_2=[1,0,1]^T$, then $\delta_{11}$ will be $2\times 2$ whereas $\delta_{12}$ will be $2\times 3$. As for $L$, this matrix contains scalar elements $l_{ij}$. For our example, let's consider $L=\begin{bmatrix} 1&-1\\-1 & 1\end{bmatrix}$. $\endgroup$ – Has Aug 6 '16 at 18:38
  • $\begingroup$ Ok, makes sense. Just checked some numerics with the e1 and e2 you gave, but different L. You get 2 evals non-zero but the relationship with spec(L) is not (yet) clear. $\endgroup$ – H. H. Rugh Aug 6 '16 at 20:03
  • $\begingroup$ Thank you professor @H.H.Rugh. Can we consider $$\begin{bmatrix} l_{11}\delta_{11} & \ldots & l_{1n}\delta_{1n} \\ \vdots & \ddots & \vdots \\ l_{n1}\delta_{n1} & \ldots & l_{nn}\delta_{nn} \end{bmatrix}$$ as a Hadamard product? We know that if $\delta_{ij}$ were scalars, that would be possible. But for this matrix, can we say the same? $\endgroup$ – Has Aug 7 '16 at 5:21
  • $\begingroup$ I don't think so. But it may share some properties with Hadamard products because of the special form for the $\delta$-matrices $\endgroup$ – H. H. Rugh Aug 7 '16 at 5:25

Denote by $\hat{L}$ the augmented matrix of size $N\times N$ where $N=d_1+\cdots + d_n$. Define the map $\Lambda : {\Bbb C}^n \rightarrow {\Bbb C}^N$ by $\Lambda (c)= \left[\begin{matrix} c_1 e_1 \\ \vdots\\ c_n e_n \end{matrix} \right]$.

The augmented matrix $\hat{L}$ maps ${\Bbb C}^N$ into ${\rm im} \Lambda$ and we have $\hat{L} \Lambda c = \Lambda H c$ where $$ H = \left( \begin{matrix} \ell_{11} (e_1^T e_1) & \cdots & \ell_{1n} (e_n^T e_n) \\ \vdots & & \vdots \\ \ell_{n1} (e_1^T e_1) & \cdots & \ell_{nn} (e_n^T e_n) \end{matrix} \right) $$ is an $n\times n$ Hadamard matrix in the usual sense. It has the same non-zero spectrum as $\hat{L}$. Oddly enough it is not symmetric?

As an example consider $$ e_1= \left[\begin{matrix} 1 \\ 0 \end{matrix} \right], e_2= \left[\begin{matrix} 1 \\ 0 \\ 1 \end{matrix} \right], Y_1= \left[\begin{matrix} y_{11} \\ y_{12} \end{matrix} \right], Y_2= \left[\begin{matrix} y_{21} \\ y_{22} \\ y_{23} \end{matrix} \right], Y= \left[\begin{matrix} Y_1 \\ Y_2 \end{matrix} \right] \in {\Bbb C}^5 .$$ The last is a column vector of length $5=2+3$. In a similar vein we write $$ X= \left[\begin{matrix} X_1 \\ X_2 \end{matrix} \right] \in {\Bbb C}^5 .$$ Acting upon $X$ with our $5 \times 5$ matrix $\hat{L}$ in question we get $Y=\hat{L} X$ where for each of the 'principal' components $$ Y_i = \sum_{j=1}^2 \ell_{ij} (e_i e_j) X_j = e_i \left( \sum_{j=1}^2 \ell_{ij} (e_j X_j)\right) \in {\rm Span} \{e_i\}.$$ So each $Y_i$ is proportional to $e_i$. In other words, $Y$ is in the image of the map $$ \Lambda : c = \left[\begin{matrix} c_1 \\ c_2 \end{matrix} \right] \in {\Bbb C}^2 \mapsto \left[\begin{matrix} e_1 c_1 \\ e_2 c_2 \end{matrix} \right] \in {\Bbb C}^5. $$ For the non-zero eigenvalues it is enough to see how $\hat{L}$ acts upon this image. So let $X_j= e_j c_j$. Then $$ Y_i = (\hat{L} X)_i= (\hat{L} \Lambda c)_i= e_i \sum_{j=1}^2 \ell_{ij} (e_j e_j) c_j = e_i \sum_{j=1}^2 H_{ij} c_j,$$ where $H$ is the 2 by 2 matrix (in our present example): $$ H = \left( \begin{matrix} \ell_{11} (e_1^T e_1) & \ell_{12} (e_2^T e_2) \\ \ell_{21} (e_1^T e_1) & \ell_{22} (e_2^T e_2) \end{matrix} \right) = \left( \begin{matrix} \ell_{11} & 2 \ell_{12} \\ \ell_{21} & 2 \ell_{22} \end{matrix} \right) $$ Whenever you have matrices verifying $\Lambda H c = \hat{L} \Lambda c$ and ${\rm im} \Lambda = {\rm im} \hat{L}$ then $H$ and $\hat{L}$ will have the same non-zero eigenvalues (fairly easy to check).

  • $\begingroup$ Thank you professor @H.H. Rugh . But, can you kindly explain more? I was trying to find a relationship between $L$ and $\Delta$. I would really appreciate it if you could shed some light on this. Thanks again $\endgroup$ – Has Aug 8 '16 at 19:54
  • $\begingroup$ Not quite sure what to say. But in the example you mentioned in a previous comment we have $e_1^T e_1=1$ and $e_2^T e_2=2$. The matrix $L$ you give then becomes $H=[1 -2; -1 2]$ ($i$th column multiplied by $e_i^Te_i$). The non-zero evals of your augmented matrix are the same as the non-zero evals of $H$ (which you may check numerically as well). Do you want more details in my calculation of $H$? $\endgroup$ – H. H. Rugh Aug 9 '16 at 8:13
  • $\begingroup$ I am guessing by $\hat L$ you are referring to $$\begin{bmatrix} l_{11}\delta_{11} & \ldots & l_{1n}\delta_{1n} \\ \vdots & \ddots & \vdots \\ l_{n1}\delta_{n1} & \ldots & l_{nn}\delta_{nn} \end{bmatrix}$$ Is that right? As a result, you say that the nonzero eigenvalues of this matrix and $$H = \left( \begin{matrix} \ell_{11} (e_1^T e_1) & \cdots & \ell_{1n} (e_n^T e_n) \\ \vdots & & \vdots \\ \ell_{n1} (e_1^T e_1) & \cdots & \ell_{nn} (e_n^T e_n) \end{matrix} \right)$$ are the same. $\endgroup$ – Has Aug 9 '16 at 18:22
  • $\begingroup$ I am so sorry, but I can't understand "The augmented matrix$\hat L$ maps $\mathbb{C}^N$into ${\rm im} \Lambda$ and we have$ \hat{L} \Lambda c = \Lambda H c $". What is $c$? I am really sorry :( but I couldn't understand the map you have defined. $\endgroup$ – Has Aug 9 '16 at 18:26
  • $\begingroup$ Your interpretation is correct. I have added details for the example you mentioned in another comment $\endgroup$ – H. H. Rugh Aug 10 '16 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.