4

$A$ is a incidence matrix for some undirected graph.

$A^TA$ is a positive definite matrix, so I know that we can factorize it as $A^TA = C + C^T$

There exists always a matrix $C$ such that $C = A^TB$? Satisfying the next requirement, $B^TB = cI$ is a diagonal matrix, being $I$ the identity matrix and $c$ a scalar, and $B$ also is related to the incidence matrix $A$ in the sense that for each edge, we select one node.

$A$ might not be square (more edges than nodes).

For instance,

$ A = \begin{bmatrix}1 & 0 & -1\\-1 & 1 & 0\\0 &-1 & 1\end{bmatrix} \quad B = \begin{bmatrix}0 & 0 & -1 \\ -1 & 0 & 0 \\ 0 & -1 & 0\end{bmatrix}, $ satisfies $A^TA=A^TB+B^TA$ and $B^TB = I$

Note that here I have taken for $B$ all the $-1$ from $A$.

Can I find such $B$ for instance for complete undirected graphs? what about for more general undirected grahps?

  • 2
    I understand that you're still thinking to make your question clearer... but what does your $A^{-T}$ mean? $(A^{-1})^{T}$? By the way there is a TeX command to do the transpose, which is \top. It looks like this : $A^{\top}$ – Patrick Da Silva May 25 '13 at 22:59
  • thanks for your comment. I have just updated the question. Now $A$ might not be a square matrix. –  May 25 '13 at 23:35
  • 1
    Do you require $B^TB$ diagonal or a scalar multiple of the identity? Note you can interpret this in terms of orthogonal columns (perhaps of the same length). Your example is rather special, since you started with an $A$ with orthogonal columns. – Ted Shifrin May 25 '13 at 23:43
  • Hi Ted, many thanks for your interest and help. Indeed, in my problem $A$ is special, it is the incidence matrix of an undirected graph. So, I can ask for being multiple of the diagonal matrix for $B^TB$. Note my last hint in the question. –  May 25 '13 at 23:47
  • 1
    Where do minus ones come from, if it's an undirected graph? – Vedran Šego May 25 '13 at 23:48
  • @Tunococ He still didn't explain if $B^TB$ has to be a multiple of an identity or can it be any diagonal matrix (including the one with some zeroes on the diagonal). – Vedran Šego May 26 '13 at 00:05
  • It is a multiple of the identity matrix. –  May 26 '13 at 00:06
  • The problem did say that $B^T B = cI$, and I believe $I$ is the identity matrix. I wrote the wrong thing though. This is the corrected statement: $B$ must have the same shape as $A$, so $B^T B = cI$ is only possible when $A$ is not a fat matrix ($A$ cannot have more columns than rows, so the original graph cannot have more edges than vertices.) – Tunococ May 26 '13 at 00:07
  • Ted, in my example $A^TB$ is [1 0 -1; -1 1 0; 0 -1 1]. It seems that $A^TB = A$, being $A$ the incidence matrix –  May 26 '13 at 00:08
  • For your example, you need something like $B=\frac12A+cE$, where $E$ is matrix of all $1$'s. (Yeah, I messed up.) Note that the vector $(1,1,\dots,1)$ is going to span the nullspace of $A^T$ for any incidence matrix $A$. – Ted Shifrin May 26 '13 at 00:10
  • So if I understand your question well, you are given a graph's incidence matrix $A$ and you want to find a matrix $B$ such that $B^{\top} B = c I$ for some scalar $c$ and $A^{\top} A = A^{\top} B + B^{\top} A$. I'm asking because the question looks hidden in your example. Is that what you want? And why would you want that? Is there some hidden motivation behind this? – Patrick Da Silva May 26 '13 at 00:21
  • 1
    My last comment seems to be necessary in general, so it's only going to work when all the off-diagonal entries of $A^TA$ are equal. This imposes some conditions on your graph, right? – Ted Shifrin May 26 '13 at 00:22
  • Hello Patrick, this is exactly my question. The motivation is because for each edge I need to select one node (the non-zero elements of $B$, such that A^TA=A^TB+B^TA –  May 26 '13 at 00:24
  • Hi Ted, this is indeed true. $A^TA$ is the Laplacian matrix, which derived from the incidence matrix $A$ (1 or -1 in/out edge), the diagonal is equal to 2$I$. –  May 26 '13 at 00:26
  • I will edit the question, with the motivation behind of it. –  May 26 '13 at 00:27
  • What if different nodes have different valences? Then the diagonal entries of $A^TA$ will be different. And if there are several edges joining a pair of nodes, this will make for different off-diagonal entries. ... I still say you want to think of $B=\frac12A+Z$ for some $Z$ whose columns are in the nullspace of $A^T$. – Ted Shifrin May 26 '13 at 01:06
  • In this case, all the valences are $1$ and $-1$ –  May 26 '13 at 01:11
  • Sorry. I mean the number of edges coming into each vertex. My vocab is not up to par. – Ted Shifrin May 26 '13 at 01:12

1 Answers1

1

If you think of this in terms of columns vectors, write $A = \begin{bmatrix} v_1 & \dots v_n \end{bmatrix}$ and $B = [ b_1 /2, \dots, b_n/2 ]$ (the one-half factor is just to normalize stuff), so that $$ A^{\top}A = [(v_i \, | \, v_j)], \qquad A^{\top} B + B^{\top} A = [(v_i \, | \, b_j/2)] + [ (b_j/2 \, | \, v_i) ] = [(v_i \, | \, b_j)]. $$ where $( \cdot \, | \, \cdot )$ denotes inner product. So you want to find $n$ column vectors $b_1,\dots, b_n$ ($n$ is the number of edges in your graph, the vectors lie in $\mathbb R^k$ where $k$ is the number of vertices) such that $$ (v_i \, | \, v_j) = (v_i \, | \, b_j). $$ In particular, if $k \le n$ and $\{ v_1, \dots, v_k \}$ forms a basis of $\mathbb R^k$, your vectors $b_j$ are completely determined by the first $k$ vectors, i.e. any set of edges which gives rise to $k$ linearly independent vectors in $\mathbb R^k$ (perhaps there is a graph-theoretic interpretation to such a constraint) determines if there exists such a matrix $B$, and what it is if it exists.

This puts a lot of constraints on the possible graphs which would acheive this, so I don't expect you to be able to find such a matrix $B$ for every graph if it has more edges than vertices in general. Otherwise these equations tell you how to compute the vectors $b_j$ ; it reduces to solve a linear system given your matrix $A$.

Hope that helps,

Patrick Da Silva
  • 41,413
  • Question : Do you want to find your matrix $B$ over $\mathbb R$ or $\mathbb C$? This would change a bit my computations. – Patrick Da Silva May 26 '13 at 00:43
  • Over $\mathcal{R}$. Note how I define the selection of $B$, it must be the selection of one of the nodes of each edge, i.e. You chose a $1$ or $-1$ for each each in $A$. –  May 26 '13 at 00:51
  • @noether : Are you disagreeing with what I said or are you saying we can still find interesting cases? I'm not following your comment very well. What is "the selection of one of the nodes of each edge"? Make it mathematically clear please... this feels vague. – Patrick Da Silva May 26 '13 at 00:52
  • Sorry Patrick, indeed your comment helps to figure out how to compute $B$. In my example, $B$ has been chosen as $A$ replacing all the $1$ by zeros. So for every edge, "we have selected the node corresponding to -1". –  May 26 '13 at 01:01
  • I'm guessing your example is a 3-cycle oriented edge. I'm guessing the $n$-cycle oriented edge will give you a matrix $B$ in the similar way. Have you tried other examples? Like say, the (oriented) complete $3$-graph? (That is, three nodes $v_1, v_2, v_3$ where there is an arrow from $v_i$ to $v_j$ for $i \neq j$.) This would be my first try if I'd like to explore what happens with this idea. – Patrick Da Silva May 26 '13 at 01:07
  • 1
    I am looking at the moment at the example of square (4 nodes) with 5 edges (perimeter + one diagonal). Lets see... –  May 26 '13 at 01:10
  • I guess my last comment is this : I have explained that it won't work in general, so if you give interest to this decomposition, you should try to compute examples and conjecture when it works, and if it means something for the graph. I think that's all I can say with what I see for now. – Patrick Da Silva May 26 '13 at 01:20
  • Agree Patrick. So far I can only find this expression for the triangle case. Thanks for your help –  May 26 '13 at 01:29