Trees and their Related Matrix Ranks

Presented by Rob Rostermundt

Background

A tree is an acyclic, connected graph.

An adjacency matrix of a graph is a {0,1} matrix in which the $ij^{th}$ entry is 1 if there is an edge between $x_j$ and $x_i$ and all other entries of the matrix are zero.

A reduced adjacency matrix for a bipartite graph is a $k\times (m-k)$-submatrix of the $m\times m$ adjacency matrix A. Its rows correspond to elements of the set $\ensuremath{\mathbb{X}}$ and its columns correspond to vertices in the set $\ensuremath{\mathbb{Y}}$. Notice that because there is no edge between any two $x_i,x_j \in \ensuremath{\mathbb{X}}$ and no edge between $y_k,y_j \in \ensuremath{\mathbb{Y}}$ the reduced adjacency matrix contains all information about the graph G.

For the same bipartite graph we can then create the reduced adjacency matrix

A biclique is a complete bipartite subgraph.


The set of darkened edges in the two following examples form biclques.

Notice that the following set of darkened edges is not a biclique.

Consider a bipartite graph B where all vertices are contained in two sets $X$ and $Y$. In the reduced adjacency matrix A(B), a biclique appears as an $m\times k$ submatrix of all ones, where $m$ is the number of vertices in the biclique contained in the set $X$ and $k$ is the number of vertices in the biclique contained in the set $Y$.

Example:

$$A(B)= \left[ \begin{array}{cccc} &&&\\ 1&&1&1\\ 1&&1&1\\ &&&\\ \end{array}\right]$$

The biclique cover number, denoted bc(G), is the smallest number of complete bipartite subgraphs that cover the edges of $G$.

Consider the following bipartite graph B. The biclique cover number or bc(B) equals 3.

The boolean rank of an $m\times n$ {0,1} matrix $A$, denoted by b(A), is the smallest number of {0,1} matrices of rank one whose boolean sum is A.

Boolean Rank, b(A), of a {0,1}-matrix A

$$A= \left[ \begin{array}{cccccc} 0&1&0&1&1&1\\ 0&0&0&1&1&1\\ 0&1&0&1&1&1\\ 0&0&0&0&0&0\\ 0&1&0&1&0&0\\ 0&1&0&1&0&0\\ \end{array}\right]$$

$$=\left[ \begin{array}{cccccc} 0&0&0&1&1&1\\ 0&0&0&1&1&1\\ 0&0... ...0&1&0&0\\ 0&0&0&0&0&0\\ 0&1&0&1&0&0\\ 0&1&0&1&0&0\\ \end{array}\right]$$

Clearly, $b(A)=2$

Theorem: $b(A)=bc(B)$

Is there a lower bound for $b(A)$?

A set $S$ of isolated 1's of a {0,1} matrix $A$ is a set where no two 1's of $S$ are in a $2\times 2$ submatrix of the form

$$\left[ \begin{array}{l r} 1&1\\ 1&1\\ \end{array} \right]$$

Example of isolated 1's of a matrix $A$

$$A=\left[\begin{array}{cccc} 0&{\bf\underline{1}}&1&1\\ {\bf\underline{1}}&0&1&1\\ 1&1&0&1\\ 1&1&1&0\\ \end{array}\right]$$

Any set $S$ of $k$ isolated ones requires at least $k$ bicliques to cover the corresponding vertices. Therefore, if $S$ is a set of isolated ones

$$\vert S\vert\le bc(B)=b(A)$$

The non-negative integer rank of an $m\times n$ matrix $A$, denoted by ${\bf r_{z^+}(A)}$ is the smallest number of rank one matrices with non-negative entries whose sum is A.

Non-negative Integer Rank, $r_{z^+}(A(B))$

$$A= \left[ \begin{array}{cccccc} 0&1&0&1&1&1\\ 0&0&0&1&1&1\\ 0&1&0&1&1&1\\ 0&0&0&0&0&0\\ 0&1&0&1&0&0\\ 0&1&0&1&0&0\\ \end{array}\right]$$

$$=\left[ \begin{array}{cccccc} 0&0&0&1&1&1\\ 0&0&0&1&1&1\\ 0&0... ...0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0\\ 0&1&0&0&0&0\\ \end{array}\right]+$$

$$\left[ \begin{array}{cccccc} 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&1&0&0\\ \end{array}\right]$$

The biclique partition number, denoted by bp(G), is the smallest number of complete bipartite subgraphs that partition the edges of $G$.

Notice that our previous example of a biclique covering was also a biclique partition.

Theorem: $bp(B)=r_{z^+}(A)$ and

$$b(A(B))=bc(B)\le bp(B)=r_{z^+}(A(B))$$

The term rank of a matrix $A$, denoted by t(A), is the smallest number of rows and columns containing all the nonzero entries of the matrix $A$.

A set of independent ones of a {0,1} matrix $A$ is a set of entries of all 1's such that no two 1's in the set are in the same row or column.

Independent 1's of a matrix $A$

$$A= \left[ \begin{array}{ccccc} {\bf\underline{1}}&1&0&1&0\\ 0&1... ...{1}}&0&1&0\\ 0&0&0&{\bf\underline{1}}&0\\ 0&1&0&0&0\\ \end{array}\right]$$

Theorem:$t(A(B))=$ maximum number of independent ones in $A(B)$.

Observe that any row or column of the matrix $A(B)$ can be viewed as a biclique in $B$. Therefore, a set of rows and columns containing all the ones in $A(B)$ will correspond to a biclique partition $B$ (where overlaps are removed). Because we could possibly find a better biclique partition,

$$r_{z^+}(A(B))\le t(A(B))$$

The real rank of an adjacency matrix $A$ is the normal rank of a matrix corresponding to the number of pivots in the matrix. It should be clear that the real rank of a matrix $A$ is less than or equal to the number of independent ones in the matrix.

We have the following bounds

$$r(A)\le t(A)$$

$$b(A) \le r_{z^+}(A) \le t(A)$$

There is no relationship between $r(A)$ and $b(A)$

Theorem: For a graph $G$ that contains no 4-cycles,

$$b(G)=r_{z^+}(G)=t(G)$$

A 4-cycle of a graph $G$ will show up as a $2\times 2$ submatrix of all ones. Therefore, given a graph $G^*$ with no 4-cycles, the adjacency matrix $A(G^*)$ will have no $2\times 2$ submatrices of all ones. It follows that every set of independent ones is also isolated. Thus

$$b(G^*)=t(G^*)$$

Therefore,

$$b(G^*)=r_{z^+}(G^*)=t(G^*)$$

Corollary: If G is C4-free then

$$r(A)\le b(A)=r_{z^+}(A)=t(A)$$

Theorem:Let $T$ be a tree with corresponding reduced adjacency matrix $A$. Then

$$r(A)=b(A)=r_{z^+}(A)=t(A)$$

proof:

It suffices to show that $r(A)=t(A)$. Do this by constructing a maximum size set $S$ of independent ones in the adjacency matrix $A$, and show that each of these ones corresponds to a pivot of the adjacency matrix $A$

The following algorithm will construct the desired set of ones.

1)Choose a path $P$ of maximum length in $T$

2)Choose a vertex $r\ne V_b$ and $r\ne V_e$

After orienting the branches of $T$ so they all hang down from the path $P$

3)Let $P_e$ be the subpath of $P$ from $r$ to $V_b$, or $r$ to $V_e$, whichever is longer

4)Label the vertices of $T$ with two subscripts, $V_{i,j}$, where $i=\vert P_e\vert-d(v,r)$ and $j=1,2,3,....,k$ for some $k$ dependent on $i$ as an enumeration of the vertices with $i$ as the initial subscript. WLOG assume that $j=1$ for all vertices in $P_e$

Notice that sets $\left\{v_{i,j}\vert\;i\mbox{ is odd}\right\}$ and $\left\{v_{i,j}\vert\;i\mbox{ is even}\right\}$ form a bipartition of the vertices of $T$

5)In the following manner, form a set of edges $S_e$ and the set of vertices $S_v$, where the vertices in $S_v$ are all the vertices incident with $S_e$

In words, construct the set $S_e$ by proceeding through the tree from bottom to top and right to left, adding edges to $S_e$ if neither of the vertices incident with this edge is already in $S_v$

In terms of the matrix $A$, this is equivalent to proceeding through the matrix from top to bottom and left to right and adding to $S$ the leftmost one that is not in a column already containing a one in the set $S$, if such a one exists.

We are now left with the following where each circled one is in the set $S$

Its clear from construction that $S$ is a set of independent ones

Before we show that $S$ is of maximum size we need the following definitions and theorem.

A matching is a set of edges of a bipartite graph where the endpoints of any edge are not incident with another edge in the set.

A vertex cover, as defined by D. West, is a set of vertices that contains at least one endpoint of every edge in $G$.

Theorem:(Koenig) Given a any vertex cover $V$ and a matching $M$, $\vert V\vert\ge \vert M\vert$

Therefore, exhibiting a vertex cover and a matching of the same size shows that each is optimal

Clearly, the set $S$ is a matching of the bipartition of $T$

To show that $S_e$ is a maximum matching we will construct a vertex cover $V$ such that $\vert V\vert=\vert S_e\vert$

Let $V=\{v_{i,j}\vert\;v_{i,j}v_{k,l}\in S_e\;and\;i>k\}$

In words, for each edge in $S_e$ put the endvertex closest to $r$ in $V$. In the previous example, $V$ consists of choosing a single vertex from each pair corresponding to each circled one. $S_e$ is a matching of $T$ and $\vert V\vert=\vert S_e\vert$. Thus, we simply need to show that $V$ is a vertex cover.

Suppose there exists an edge $v_{i,j}v_{i-1,k}\in T$ with $i>2$ such that $v_{i,j}$ and $v_{i-1,k}$ are not in $V$. Then edge $v_{i-1,k}v_{i-2,m}\not\in S_e$, for $v_{i-2,m}\in N(v_{i-1,k})$ guaranteeing that $v_{i-1,k}\not\in S_v$. The same argument guarantees that no edge of the form $v_{i,j}v_{i-1,u}$ will be in $S_e$ when $v_{i-1,u}\in N(v_{i,j})$. But by the construction algorithm every $v_{i-1,u}$ must then be in $S_v$ for $u<k$.

Therefore, $k=min\{s\;\vert\;v_{i-1,s}\in N(v_{i,j})\}$ and $v_{i,j}v_{i-1,k}$ would have been chosen for $S_e$

Next suppose that there is an edge $v_{2,j}v_{1,k}\in T$ such that $v_{2,j}\not\in V$. Since $v_{2,j}$ is not in $V$ we are assured that $v_{2,j}v_{1,k}\not\in S_e$ for any $u$ such that $v_{i,u}\in\;N(v_{2,j})$. The same argument from above forces $v_{2,j}v_{1,k}$ to be in $S_e$ which is a contradiction.

Therefore, all edges of $T$ are covered by $V$ and $V$ is a vertex cover such that $\vert V\vert=\vert S\vert$ and $S$ is a matching of maximum size.

Lastly, we need to show that the ones in $S$ correspond to pivots of $A$

Notice that in each column, there is at most a single circled one from the set $S$. Therefore, the first step is to use elementary row operations to zero out any ones below a circled one. We need to guarantee that these row operations will not change any row except to zero out the intended one. We do this by showing that there may be no submatrices of the following forms

$$A= \left[ \begin{array}{cc} 1&1\\ 1&1\\ \end{array}\right] \hspace*{2cm} A= \left[ \begin{array}{cc} 1&1\\ 1&0\\ \end{array}\right]$$

where the upper left one is in the set $S$.

The submatrix of all ones can not exist due to the lack of 4-cycles.

The other submatrix form must be eliminated by two cases.

By use of the algorithm that forms the bipartition of $T$, a vertex $v_{i,j}$ may only be in the neighborhood of a vertex with index $v_{i-1,m}$ or $v_{i+1,k}$. Also, assume that the rows of the matrix represent vertices with $i$ odd and the columns of the matrix represent vertices with $i$ even. The matrix columns and rows are also enumerated in order with the second index $j$.

Let $v_{i,j}$ be the row labeling for the one in the upper left position of the forbidden submatrix. The one in the bottom left position must have a row index $v_{i,k}$ or $v_{i+2,l}$. Assuming that the second vertex has a row index $v_{i,k}$, both $v_{i,j}$ and $v_{i,j}$ must be pendant vertices hanging from a vertex $v_{i+1,m}$. This follows since there are no cycles in the graph $T$. Then a one in the upper right entry of the submatrix would force another edge $v_{i,j}v_{i+1,u}$, inducing a cycle in the graph and this is a contradiction.

Assume that the bottom-left entry in the forbidden subgraph had a row index $v_{i+2,l}$. Then by the restrictions on what indices can match up with a one in the matrix, the first column index is forced to be $v_{i+1,m}$ once again. The same argument as above guarantees that there can be no one in the top-left entry of the submatrix.

These two cases assure us that there can be no submatrix of the form

$$A= \left[ \begin{array}{cc} 1&1\\ 1&0\\ \end{array}\right]$$

and elementary row operations will only zero out the intended one.

Now every one in the set $S$ will have zero's to its left and zero's underneath and we may now exchange rows and finish in the form

$$A= \left[ \begin{array}{cccccccc} 1&.&.&.&.&.&.&.\\ 0&0&1&.&.&.... ... 0&0&0&1&.&.&.&.\\ 0&0&0&0&0&1&.&.\\ 0&0&0&0&0&0&0&0\\ \end{array}\right]$$

where each pivot corresponds to a one in the set $S$. Hence, $r(A)\ge t(A)$ and from our corollary we have

$$r(A)=b(A)=r_{z^+}(A)=t(A)$$

Q.E.D