3
$\begingroup$

Let me be more specific: If $A=BC$, where $A$ and $C$ are given Laplacian matrices, how to calculate $B$? The graph corresponding to $A$ is a directed ring, which is strongly connected and $1_n$ and $1_n^T$ are right and left eigenvectors respectively. The graph corresponding to $C$ is a weighted directed ring, which is strongly connected but $1_n^T$ is no longer its left eigenvecor while $1_n$ is still its right eigenvector.

For example, $A=\left[ \begin{array}{ccc} 1&-1&0\\0&1&-1\\-1&0&1\end{array} \right]$, that is , $A$ is a circulant ,singular, Laplacian matrix. $C=\left[ \begin{array}{ccc} 1&-1/2&-1/2\\-2/3&1&-1/3\\-4/5&-1/5&1\end{array} \right]$ (singular, non-symmetric Laplacian matrix). Then how to compute $B$ if $A=BC$.

Note that $A, B, C$ are all square matrices. I don't want numerical solutions. There may be many solutions to this problem, so is there a formulated way to find one of them (maybe we can restrict $B$ to be Laplacian as well)?

$\endgroup$
  • 1
    $\begingroup$ Vectorizing the matrix equation, we obtain the linear system $$\rm (C^{\top} \otimes I) \, \mbox{vec} (B) = \mbox{vec} (A)$$ From here on, use Gaussian elimination, for instance. $\endgroup$ – Rodrigo de Azevedo Mar 2 '17 at 9:41
  • $\begingroup$ @RodrigodeAzevedo On a singular matrix? $\endgroup$ – Federico Poloni Mar 2 '17 at 9:48
  • 1
    $\begingroup$ @RodrigodeAzevedo 1. It's an ill-posed problem. The solution is not unique. Assuming that limit exists, it only gives you one. OP should specify more about the solution they want. What if $A=C=0$, for instance? 2. Vectorizing seems useless - you can simply solve that equation row by row, dealing with $n\times n$ matrices instead of $n^2\times n^2$. 3. This question seems off-topic here in the present form. No motivation, badly specified (are the matrices square? Numerical solution or closed formula?), no hint of trying some basic linear algebra to deal with the singular system. $\endgroup$ – Federico Poloni Mar 2 '17 at 10:11
  • 2
    $\begingroup$ @RodrigodeAzevedo I have updated my question. Note that the Laplacian does not necessarily correspond to a undirected graph, which means the Laplacian is not necessarily symmetric and therefore $1_n^T$ is not necessarily its left eigenvector. In this case, $1_n^T$ is not the left eigenvector of $C$. $\endgroup$ – winston Mar 4 '17 at 12:33
  • 1
    $\begingroup$ I voted for reopening (3 now), and I'd answer if this was reopened. Quick version: chop off the last column of $C$ and $A$, which is superfluous because it's an equation that can be obtained by summing the others. Call $\hat{A}$, $\hat{C}$ the results. Now you can use (transposing) the formula for the pseudoinverse of a non-rank-deficient matrix, i.e., $B = \hat{A}\hat{C}^*(\hat{C}\hat{C}^*)^{-1}$, or normalize the last column of $A$ to be $1$ and solve the remaining $(n-1)\times(n-1)$ nonsingular linear systems for each row. $\endgroup$ – Federico Poloni Mar 5 '17 at 12:48
2
$\begingroup$

If the system of linear equations is consistent, its solution is $B=AC^+$, where $C^+$ is the pseudoinverse of $C$. Depending on the strictness of your definition of "closed formula", this may already fit the requirements. Otherwise, there are more explicit expressions. I list three alternatives in the following. Divide $A$ and $C$ into blocks $$ \begin{bmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{bmatrix} =\begin{bmatrix} B_{11} & B_{12}\\ B_{21} & B_{22} \end{bmatrix} \begin{bmatrix} C_{11} & C_{12}\\ C_{21} & C_{22} \end{bmatrix}. $$ where the blocks labeled $22$ are $1\times 1$. Note that $C_{11}$ is invertible, because it is a submatrix of a singular irreducible M-matrix.

  1. Remove the last column, which is superfluous since it is the opposite of the sum of the previous ones, to obtain the reduced linear system $$ \begin{bmatrix} A_{11}\\ A_{21} \end{bmatrix} =\begin{bmatrix} B_{11} & B_{12}\\ B_{21} & B_{22} \end{bmatrix} \begin{bmatrix} C_{11}\\ C_{21} \end{bmatrix}. \tag{*} $$ Now you can use the formula for the pseudoinverse of a matrix with linearly independent columns $$ B = \begin{bmatrix} A_{11}\\ A_{21} \end{bmatrix} \begin{bmatrix} C_{11}\\ C_{21} \end{bmatrix}^+ = \begin{bmatrix} A_{11}\\ A_{21} \end{bmatrix} \left(\begin{bmatrix} C_{11}\\ C_{21} \end{bmatrix}^*\begin{bmatrix} C_{11}\\ C_{21} \end{bmatrix}\right)^{-1}\begin{bmatrix} C_{11}\\ C_{21} \end{bmatrix}^*. $$
  2. Once you have removed the last column, you can choose $B_{12}$ and $B_{22}$ arbitrarily and solve for $B_{11}$, $B_{21}$ in (*), which is possible since $C_{11}$ is invertible.
  3. If $u,v$ are norm-1 vectors such that $Cv=0, u^*C=0$, then another formula for the pseudoinverse is $$ C^+ = (C + uv^*)^{-1}-vu^*. $$ You can prove this using the formula for $C^+$ based on the SVD of $C$ -- basically the idea is that we change the last singular value of $C$ from $0$ to 1, then invert, and undo the change.
$\endgroup$
  • $\begingroup$ But $AC^{+}$ is no longer a Laplacian.... $\endgroup$ – Felix Goldberg Mar 14 '17 at 10:01
  • 2
    $\begingroup$ @FelixGoldberg OP asked for a closed formula for any solution to the system, if I understand correctly. In any case, if one wants a Laplacian, it is easy to enforce it: the general solution is $B=AC^+ + xu^*$, where $x\in\mathbb{R}^n$, and we can determine $x$ by enforcing $B1_n = 0$. This condition gives a valid choice of $x$ because $u^*1_n \neq 0$, as $u$ can be chosen with positive entries by Perron-Frobenius. $\endgroup$ – Federico Poloni Mar 14 '17 at 10:54
  • $\begingroup$ $CC^+$ does not necessarily equal to the identity matrix so $B=AC^+$ is incorrect. $\endgroup$ – winston Mar 15 '17 at 2:23
  • $\begingroup$ @winston $CC^+\neq I$ if $C$ is singular, yet that formula produces one of the solutions to the linear system (when it is solvable). See this paragraph or a textbook on applied linear algebra (such as Demmel or Trefethen-Bau). $\endgroup$ – Federico Poloni Mar 15 '17 at 7:13

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.