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)?

Improve this question
$\endgroup$
19
  • 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
    Commented Mar 2, 2017 at 9:41
  • $\begingroup$ @RodrigodeAzevedo On a singular matrix? $\endgroup$
    – Federico Poloni
    Commented Mar 2, 2017 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
    Commented Mar 2, 2017 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
    Commented Mar 4, 2017 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
    Commented Mar 5, 2017 at 12:48

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$
4
  • $\begingroup$ But $AC^{+}$ is no longer a Laplacian.... $\endgroup$
    – Felix Goldberg
    Commented Mar 14, 2017 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
    Commented Mar 14, 2017 at 10:54
  • $\begingroup$ $CC^+$ does not necessarily equal to the identity matrix so $B=AC^+$ is incorrect. $\endgroup$
    – winston
    Commented Mar 15, 2017 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
    Commented Mar 15, 2017 at 7:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .