Rank of a graph matrix

Question

$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$. There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th digit of the binary representation of $j$ is $0$ or $(i-m+1)$'th bit is $1$. In other words, each of the $2m$ nodes on the left corresponds to a position from $\left \{ 0,\cdots ,m-1 \right \}$ and a bit value from $\left \{ 0,1 \right \}$, and each node on the right is connected to exactly $m$ nodes on the left corresponding to the binary representation of its index. Now, given the above graph, we define matrix $A_{m*m}$ as following: $a_{i,j} =$ # of paths of length 2 connecting $u_i$ to $u_j$. The question is what is the rank of matrix $A$?

Answer 1

If I understand the problem correctly, you can determine not only the rank of $A$ but also its eigensystem. I'm assuming that "digit" and "bit" mean the same thing in your problem statement, and the only difference between the first half and the second half of the nodes on the left is whether a $0$ bit or a $1$ bit is required at the corresponding bit position in the index of the right-hand node.

Each node on the left is connected to $2^{m-1}$ nodes on the right that have a particular bit at a particular bit position. In general, the conditions for two different nodes on the left are independent of each other, so they have half their right-hand nodes in common, i.e. they are connected by $2^{m-2}$ paths of length $2$. The only exception is when the two nodes refer to the same bit. If they refer to the same bit and one requires a $0$ and the other requires a $1$, then these conditions contradict each other, and they are connected by $0$ paths of length $2$. If they both require the same bit value, they are in fact the same node, and in this case there are $2^{m-1}$ paths of length $2$, one for each right-hand node that the node is connected to. In summary:

$$a_{i,j}=\left\{\begin{array}{l}2^{m-1}\;\;\mathrm{for}\;\;i=j\\\ 0\;\;\mathrm{for}\;\;\lvert i-j\rvert=m\\\ 2^{m-2}\;\;\mathrm{otherwise} \end{array}\right.$$

That means $A$ has a block structure; it consists of four square blocks of equal size, each of which has constant entries $2^{m-2}$ except for the diagonal entries, which are $2^{m-1}$ in the blocks on the diagonal and $0$ in the blocks off the diagonal. By symmetry, such a matrix of the form

$$\left(\begin{array}{cc}B&C\\C&B\end{array}\right)$$

has $m$ eigenvectors of the form

$$\left(\begin{array}{c}\vec{x}\\\vec{x}\end{array}\right),$$

where $\vec{x}$ is an eigenvector of $B+C$, and $m$ eigenvectors of the form

$$\left(\begin{array}{c}\vec{x}\\-\vec{x}\end{array}\right),$$

where $\vec{x}$ is an eigenvector of $B-C$.

In the present case, $B-C$ is just $2^{m-1}$ times the identity matrix, so we get $m$ eigenvectors with eigenvalue $2^{m-1}$.

$B+C$ is a constant matrix with entries $2^{m-1}$, so we get one eigenvector with eigenvalue $m2^{m-1}$ and an $(m-1)$-dimensional eigenspace of vectors that sum to zero with eigenvalue $0$.

Thus, the rank of the matrix is $m+1$.

[Update in response to the question about base 4 in the comment:]

You can apply similar reasoning in the base 4 case. The matrix entries in this case are

$$a_{i,j}=\left\{\begin{array}{l}4^{m-1}\;\;\mathrm{for}\;\;i=j\\\ 0\;\;\mathrm{for}\;\;m \mid i-j\;\; (i\neq j)\\\ 4^{m-2}\;\;\mathrm{otherwise} \end{array}\right.$$

This matrix has the form

$$\left(\begin{array}{cccc} B&C&C&C\\\ C&B&C&C\\\ C&C&B&C\\\ C&C&C&B \end{array}\right)\;,$$

and by symmetry there are $m$ eigenvectors each of the form

$$\left(\begin{array}{c} \vec{x}\\\ \mathrm{i}^k\vec{x}\\\ \mathrm{i}^{2k}\vec{x}\\\ \mathrm{i}^{3k}\vec{x}\\\ \end{array}\right),$$

with $k=0,1,2,3$, where $\vec{x}$ is respectively an eigenvector of $B + (\mathrm{i}^k + \mathrm{i}^{2k} + \mathrm{i}^{3k})C$. Analogously to the base 2 case, this leads to one constant matrix for $k=0$ and three multiples of the identity matrix for $k=1,2,3$, resulting in rank $3m+1$. More generally, for base $b$, this argument shows that the rank of the matrix is $(b-1)m+1$.