Person i belongs to a clique iff ith diagonal entry of B^3 is positive

[psie]

Homework Statement

In my linear algebra book they gave some applications to composition of linear maps, and I found the following exercise.

Exercise. For an incidence matrix $A$ with related matrix $B$ defined by $B_{ij}=1$ if $i$ is related to $j$ and $j$ is related to $i$, and $B_{ij}=0$ otherwise, prove that $i$ belongs to a clique if and only if $(B^3)_{ii}>0$.

Relevant Equations

See below.

An incidence matrix reflects a relation on a set of $n$ objects $1,2,\ldots,n$ and is a square matrix with $0$s on the diagonal, and $0$s and $1$s elsewhere. For example, consider the incidence matrix $$A=\begin{pmatrix}0&1&0&0\\ 1&0&0&1 \\ 0&1&0&1 \\ 1&1&0&0\end{pmatrix}.$$Since $A_{34}=1$ and $A_{14}=0$, person $3$ can send to $4$ but $1$ can not send to $4$. The interpretation of $(A+A^2+\cdots+A^m)_{ij}$ is the number of ways in which person $i$ can send to $j$ in at most $m$ stages. If you compute $A^2$, you will see that $(A^2)_{31}=2$, so there are two ways in which person $3$ can send to $1$ in at most two stages

A clique is a maximal collection of three or more people with the property that any two can send to each other. So according to the exercise above, if you're given an incidence matrix $A$ and compute $B$ and then $B^3$, we have person $i$ is in a clique if and only if $(B^3)_{ii}>0$.

I don't really know where to start with this exercise. I know no graph theory and the book hasn't presented any. I notice it is an if and only if statement, so there are two implications I need to prove. Also, $B$ is symmetric. Grateful for any help.

 

[fresh_42]

We need to show that
$$\sum_{r=1}^n \sum_{k=1}^n b_{ik}b_{kr}b_{ri} > 0.$$
I would first try an induction and hope to get a clue how it can generally be done from $n=2$ or $n=3.$ It seems we need an interpretation of what the (sum of the) products mean.

Another idea is to investigate the opposite case. Since all entries are either one or zero, there are not many possibilities for the sum to become zero.

The Cholesky decomposition could also possibly help.

 

[fresh_42]

I know no graph theory and the book hasn't presented any.

Good for you. I have searched the internet and found myself in very deep rabbit holes of likewise complexity theory or graph theory. One paper started with 16(!) definitions before it even began to prove something. And none of it had a matrix to the power of three.

Maybe this could help (not very detailed but it contains some context):
https://brainly.com/textbook-solutions/q-20-incidence-matrix-related-matrix-b-defined

 

[psie]

We need to show that
$$\sum_{r=1}^n \sum_{k=1}^n b_{ik}b_{kr}b_{ri} > 0.$$
I would first try an induction and hope to get a clue how it can generally be done from $n=2$ or $n=3.$ It seems we need an interpretation of what the (sum of the) products mean.

Here's my progress so far. A clique is by definition a collection of three or more people such that any two of them can send to each other. So if $n=4$, and person $i$ belongs to a clique, then there must exist at least two indices $j,l$ such that $b_{ij}=b_{ji}=b_{il}=b_{li}=1$. However, if person $i$ is related to $j$ and $l$, aren't $j$ and $l$ related to each other, so that $b_{jl}=b_{lj}=1$? If so, then $$\sum_{r=1}^n \sum_{k=1}^n b_{ik}b_{kr}b_{ri} > 0,$$since it contains the term $b_{ij}b_{jl}b_{li}=1$ by letting $k=j$ and $r=l$. If this is correct, this proves one direction of the equivalence in the exercise I think.

 

[psie]

Actually, forget what I wrote in post #4. After having forced myself to watch some videos on graph theory real quick, it makes more sense now (though the terminology in this exercise is a bit different than the standard one). I think $B$ is called an adjacency matrix and the interpretation of $(B^k)_{ii}$ is the number of walks of length $k$ from $i$ to $i$ in the graph representing $B$. Then if $i$ is in some clique, which contains three or more vertices, it has to belong to a triangle in the graph, i.e. there is a walk of length 3 from $i$ to $i$ (so that $(B^3)_{ii}>0$). I'll leave the converse as an exercise.

 

[FactChecker]

Actually, forget what I wrote in post #4. After having forced myself to watch some videos on graph theory real quick, it makes more sense now (though the terminology in this exercise is a bit different than the standard one). I think $B$ is called an adjacency matrix and the interpretation of $(B^k)_{ii}$ is the number of walks of length $k$ from $i$ to $i$ in the graph representing $B$. Then if $i$ is in some clique, which contains three or more vertices, it has to belong to a triangle in the graph, i.e. there is a walk of length 3 from $i$ to $i$ (so that $(B^3)_{ii}>0$). I'll leave the converse as an exercise.

That is what I thought, but usually a clique is defined so that there can be a two-vertex clique. In that case, I think the statement is false.

 

[fresh_42]

At least I learned that CLIQUE is NP-complete.

 

[pasmith]

If i is not in a clique, then either it is isolated (so the only path from i to i is of length zero) or it is associated with one other element, so that the only path from i to itself is of length 2.

Given that this is a linear algebra text, you are probably expected to use linear algebra techniques to solve it. For example, you could use a change of basis to move entreis involving element i and any associated elements to the top left of the matrix; the effect of this is to permute the diagonal elements. Then you can consider what the top left 3x3 block of the transformed matrix must look like if i is or is not in a clique, and so determine what the top left 3x3 block of the cube must be.

 

[WWGD]

At least I learned that CLIQUE is NP-complete.

Well, if P=NP, Encryption/Decryption will be in P. Implications of it don't seem positive overall.

 

[fresh_42]

Well, if P=NP, Encryption/Decryption will be in P. Implications of it don't seem positive overall.

As far as real world applications are concerned, it will be a matter of the degree of that polynomial.

I would like to see P=NP or a zero that is not on the critical line, but that's because of my wish to see a lot of people being very surprised, and not really a hope.