Results

From the stated definitions we can introduce some known bounds on covering and partition numbers and also certain ranks of an adjacency matrix M for a tournament T.

1) $bc(T)\le bp(T)$ and $b(M)\le r_{\ensuremath{\mathbb{Z^+} } }(M)\le t(M)$

2) $r(M)\le r_{\ensuremath{\mathbb{Z^+} } }(M) \le t(M)$

There is no relationship between r(M) and b(M).

We now look at some results concerning the basic problem which asks for which tournaments are all or some of these values equal? The first theorem gives us a lower bound on the real rank of M and therefore a lower bound on the non-negative integer rank and the term rank of M.

1) If A is an n-tournament matrix, then $r(A)\ge n-1$. The proof involves 3 lemmas proven with linear algebra techniques. Before introducing the lemmas, recall also the following matrix definitions.


Definition: If a matrix A is skew-symmetric, then given the a_ij entry of matrix A, the a_ji entry of the matrix A^T equals -a_ij. Therefore, A=-A^T.

Definition: A matrix A is nonsingular if and only if A is invertible.

Definition: The adjacency matrix for a tournament graph is a tournament matrix.

Lemma 1: Suppose that a tournament matrix A is a skew-symmetric matrix. Then the matrix A+I is nonsingular.


proof:

Let A be a skew-symmetric matrix and show that I+A is invertible, and so non-singular. Because addition with A and I is defined, A must be $n\times n$ and is also an operator. It is a well known result that given an operator $T:V \longrightarrow V$ the following statements are equiavalent:

i) T is invertible
ii) T is injective
iii) T is surjective

Therefore, we will show that I+A is injective.

Choose some vector $v\in$ null(I+A). Then $(I+A)v=0 \longrightarrow Iv+Av=0$. Expanding (I+A)V=0 results in the following:

$$\begin{eqnarray*}Av&=&-v\\ (Av)^T&=&-v^T\\ v^TA^T&=&-v^T\;\;(*)\\ \end{eqnarray*}$$

From A=-A^T, we also know the following:

$I+A=I-A^T \longrightarrow \mbox{null}(I+A)=\mbox{null}(I-A^T)$

Therefore, for this same $v\in$ null(I+A), (I-A^T)v=0, and expanding (I-A^T)v=0 we obtain

$$\begin{eqnarray*}Iv-A^Tv&=&0\\ A^Tv&=&v\\ \end{eqnarray*}$$

Now simply multiply both sides of the equation on the left by v^T to get

$$\begin{eqnarray*}v^TA^Tv&=&v^Tv\\ \end{eqnarray*}$$

But v^TA^T=-v^T from equation (*) above and then

$$\begin{eqnarray*}-v^Tv&=&v^Tv\\ -<v,v>&=&<v,v>\\ \end{eqnarray*}$$

The only way for the inner product of v with itself to be its negative is for v=0. Therefore, for any vector $v\in$ null(I+A), v=0 and

$$\mbox{null}(A)=\{0\}$$

Therefore, (I+A) is injective and (I+A) is non-singular.

Lemma 2: Given two matrices A and B,

$$r(A+B)\le r(A)+r(B)$$

proof:


Let $\{v_1,v_2,...,v_k\}$ be a basis for the column space of A and let
$\{w_1,w_2,...,w_m\}$ be a basis for the column space of B.

Then the column space of (A+B) is spanned by these vectors. Thus

$$\{v_1,v_2,...,v_k,w_1,w_2,...,w_m\}\mbox{ span the column space of }(A+B)$$

and

$$\mbox{dim column space of }(A+B)\le k+m$$

$$\mbox{and therefore } r(A+B)\le k+m=r(A)+r(B)$$

Q.E.D

This next lemma follows directly from lemma 3 after rearranging terms.

Lemma 3: Given two matrices Aand B,

$$r(A-B)\ge r(A)-r(B)$$

proof: This is equivalent to proving $r(A)\le r(A-B)+r(B)$
Notice we can rewrite r(A) as the following.

$$\begin{eqnarray*}r(A)&=&r(A-B+B)\\ &\le&r(A-B)+r(B)\mbox{ (from Lemma 2)}\\ \end{eqnarray*}$$

Therefore, $r(A-B)\ge r(A)-r(B)$.

Q.E.D.

Next we can use these three results to prove the following theorem.

Theorem 4.1 : If M is an n-tournament matrix, then

$$n-1\le r(M)\le n$$

proof:

For any tournament matrix M we know that M+M^T=J-I, where J is the matrix of all 1's. (See Figure 3.4) What are the possible ranks of M?

$$M+M^T=J-I \Longrightarrow J=I+M+M^T$$

Look at the matrix M-M^T and its transpose.

(M-M^T)^T=M^T-M=-(M-M^T)

Therefore, M-M^T is skew-symmetric and the following argument follows.

$$\begin{eqnarray*}& A=I+M-M^T\mbox{ is non-singular (by lemma 1)}\\ \end{eqnarray*}$$

Therefore r(A)=n, and

$$\begin{eqnarray*}& r(A-J)\ge r(A)-r(J)\ge n-1 \mbox{ (by lemma 3)}\\ \end{eqnarray*}$$

But, $J=I+M+M^T\mbox{ and }A=I+M-M^T$ gives us

A-J=-2M^T

$$\Longrightarrow r(M)=r(M^T)\ge n-1$$

Q.E.D.

Knowing that $r(A)\ge n-1$ for an $n\times n$ tournament matrix A, the null space of a singular tournament matrix is spanned by exactly one vector. A logical question then follows: What type of tournaments have adjacency matrices with r(A)=n. Theorem 4.? will show that all regular tournaments are nonsingular.

A tournament is regular if all its vertices have equal scores, meaning that all row sums of the matrix are equal. If A is a regular n-tournament then n must be odd. In order to prove this result, we use a lemma proved by Maybee and Pullman


Lemma: If $\ensuremath{\vec{x}} =(x_1,x_2,...,x_n)^T$ spans the null space of an n-tournament matrix, then

$$\left(\sum^n_{i=1}x_i\right)^2=\sum^n_{i=1}x_{i}^2$$

proof: Notice that

$$\begin{eqnarray*}\sum^n_{i=1}{x_i}^2&=&{x_1}^2+{x_2}^2+...+{x_n}^2\\ &=&<x,x>\\ &=&x^Tx\\ \end{eqnarray*}$$

We also have the following property of tournament matrices

M+M^T=J-I

Choose $x\in$ null(M). Then $x^T\in$ null(M^T) and the following holds

$$\begin{eqnarray*}Mx+M^Tx&=&Jx-Ix\\ M^Tx&=&Jx-x\\ x&=&(J-M^T)x \end{eqnarray*}$$

Left multiply by x^T to obtain

$$\begin{eqnarray*}x^Tx&=&x^T(J-M^T)x\\ &=&x^TJx-x^TM^Tx\\ &=&x^TJx\\ \end{eqnarray*}$$

Recall that J is the all-ones matrix, and that J²=nJ. Thus

$$Jx=\left(\begin{array}{c} \sum^n_{i=1}x_i\\ .\\ .\\ .\\ .\\ .\\ \sum^n_{i=1}x_i\\ \end{array}\right)$$

and

$$\begin{eqnarray*}% latex2html id marker 586 (Jx)^TJx&=&x^TJJx\\ &=&x^TJ^2x\\ &=&x^TnJx\\ &=&nx^TJx\\ &=&nx^Tx\mbox{ (from equation?) }\\ \end{eqnarray*}$$

Jx is just a vector and so (Jx)^TJx=<Jx,Jx>. Therefore

$$(Jx)^TJx=\left(\sum^n_{i=1}x_i\right)+...+\left(\sum^n_{i=1}x_i\right)^2= n\left(\sum^n_{i=1}x_i\right)^2$$

Thus $n\left(\displaystyle\sum^n_{i=1}x_i\right)^2=nx^Tx$, and

$$\left(\sum^n_{i=1}x_i\right)^2=x^Tx=\sum^n_{i=1}{x_i}^2$$

Q.E.D.

Having proved the previous lemmas we are now set up to prove the following theorem about the real rank of a tournament matrix. Then we we can use this result to prove some purely graph theoretic results that would be extremely difficult to show using just graph theory.

Theorem 4.2 : A regular tournament matrix is nonsingular.


proof: Let A be a regular n-tournament matrix and let $\ensuremath{\vec{v}} =(v_1,v_2,...,v_n)^T$ be a vector such that $A\ensuremath{\vec{v}} =0$. Then

$$A=\left( \begin{array}{c} v_1\\ v_2\\ .\\ .\\ .\\ v_n\\ \end... ...( \begin{array}{c} 0\\ .\\ .\\ .\\ .\\ 0\\ \end{array}\right)$$

where $A_j=\{i=j\to i\}$. This implies that

$$\displaystyle\sum_{i\in A_i}v_i+...+\displaystyle\sum_{i\in A_n}v_i=0$$

In the previous sum, each v_i must appear exactly $$\frac{n-1}{2}$$times which corresponds to the number of vertices which beat vertex i. Thus,

$$\displaystyle\frac{n-1}{2}(v_1+...+v_n)=0$$

$$\sum^n_{i=1}v_i=0$$

$$\left(\sum^n_{i=1}v_i\right)^2=0$$

$$\sum^n_{i=1}{v_i}^2=0$$

The rows of the matrix each correspond to a vertex in G, and are partitioned in to the sets $\ensuremath{\mathbb{X} }$ and $\ensuremath{\mathbb{Y} }$ such that the first krows will relate to $\ensuremath{\mathbb{X} }$ and the remaining m-k rows relate to $\ensuremath{\mathbb{Y} }$. The definition also holds for the columns resulting in a $n\times n$ tournament matrix.

v=0

Therefore, A is non-singular



Here is a more generalized proof using what is called a pseudo-tournament matrix M, where M is defined to be a square complex matrix with rank (M+M^T+I)=1. It is easy to verify that a $n\times n$ real-matrix M is a pseudo-tournament matrix if and only if

M+M^T+I=hh^T

for some non-zero vector h.


Theorem 4.3 : If $\lambda$ is an eigenvalue of the $n\times n$pseudo-tournament matrix M, then either rank $(M-\lambda I)=n-1$ or $\lambda=-\displaystyle\frac{1}{2}$

proof: Let H=M+M^T+I. Then H= hh^T for some $h\ne 0$. For every $v\in \mathbb{R} ^n$, let s(v)=h^Tv=<h,v>. If we choose x as an eigenvector corresponding to $\lambda$, we have

$$\lambda x+M^Tx+x= hs(x)$$

Recall that M is a matrix over $\mathbb{R}$ and so $x^TM^T=\lambda x^T$. Therefore, multiplying by x^T we obtain the following

$$\begin{eqnarray*}x^T\lambda x + x^TM^Tx+x^Tx&=&x^Ths(x)\\ \lambda x^Tx+\lambda ... ...)\\ (2(\lambda)+1)\mid\mid{x}\mid\mid^2&=&\pm\mid s(x)\mid^2\\ \end{eqnarray*}$$

If $\lambda$'s eigenspace has dimension greater than 1, then there must be a vector $y\ne 0$ that is orthoganol to x. Therefore,

$$\begin{eqnarray*}y^T\lambda x+y^TM^Tx+y^Tx&=&y^Ths(x)\\ \lambda y^Tx+\lambda y^Tx+y^Tx&=&(h^Ty)^Ts(x)\\ 0+0+0&=&s(y)s(x)\\ \end{eqnarray*}$$

$$0=s(y)s(x) \Longrightarrow 2(\lambda)+1=0$$

and $\lambda=-\displaystyle\frac{1}{2}$

Q.E.D.

Theorem 4.4 : If M+M^T+I+J and the row sums of M are constant, then M is non-singular.

proof: We can define the all-ones matrix J alternatively as jj^T where j=(1,1,...,1)^T.Then clearly Mj=kj where k is the constant row sum of M. It also follows that j^TM^T=k^*j^T=kj^T. Then

Mj+M^Tj+j=jj^Tj

gives us that kj+M^Tj+j=jn=nj. Left-multiply by j^T to get

$$\begin{eqnarray*}j^Tkj+j^TM^Tj+j^Tj&=&j^Tnj\\ kj^Tj+kj^Tj+j^Tj&=&nj^Tj\\ kn+kn+n&=&n^2\\ n(2k)&=&n(n-1)\\ 2k&=&n-1\\ \end{eqnarray*}$$

Therefore, 2(k)=n-1.

Notice that for a regular tournament matrix $k=\displaystyle\frac{n-1}{2}$always holds. So assuming M is a tournament matrix allows us to shorten the proof dramatically starting here.

Lets choose $x\in null(M)$ so Mx=0. From Theorem 4.3 are left with M^Tx+x=js(x). Then

$$\begin{eqnarray*}j^TM^Tx+j^Tx&=&j^Tnx\\ k^Tj^Tx+j^Tx&=&nj^Tx\\ (k^T+1-n)(j^Tx)&=&0\\ \end{eqnarray*}$$

But from above 2(k)=n-1 and therefore,

$$k+1-n\ne 0$$

If follows that $j^Tx=0 \Longrightarrow n\mid\mid x\mid\mid^2=\mid j^Tx\mid=0$ which forces x=0.

Therefore, $null(M)=\{0\}$ and since M is an operator M must also be non-singular. A regular tournament matrix is a {0,1} square matrix with equal row sums. Thus it follows that all regular-tournament matrices are non-singular.

Q.E.D.

Corollary: If A is a regular n-tournament matrix, then

r(A)=r_z⁺(A)=t(A)=n

Next we look at a result that was originally proved in 1971. The original proof was done similarly using linear algebra and the adjacency matrices. However the techniques were far more difficult. Using this bound on the real rank of a tournaments adjacency matrix allows a short and clear proof. There has never been a purely graph theoretic proof of this result.

Corollary: (Graham and Pollack [1971]) Let the complete graph K_n have a decomposition G₁,G₂,...,G_r into complete bipartite subgraphs. Then $r\ge n-1$

proof: It is simple to get a decomposition for r=n-1. Look at the following graph K₅

Let $G_1=\{K_1,n-1\}$, the complete bipartite graph on one vertex with n-1 edges, be the following bipartite graph

Let $G_4=\{K_1,1\}$, the complete bipartite graph on one vertex with one edge, be the following

For each G_i direct the edges from one set of the bipartition to the other set. This gives a directed biclique partition of a tournament T with adjacency matrix M. Recall that $bp(T)=r_{\ensuremath{\mathbb{Z^+} } }(M)$.

Then,

$$r\ge bp(T)=r_{\ensuremath{\mathbb{Z^+} } }(M)\ge r(M)\ge n-1$$

The original decomposition might not be as easy to obtain as this. However, using any partition and directing the edges of the subsequent subgraphs gives us a tournament and its clear that the result will hold for any tournament.

This is a surprising result. It is easy to see with smaller size tournaments, but picture a tournament on 100 vertices. With so many edges in the graph, it would seem that we could take a large partition G₁, of say 50 edges, and then be able to partition the rest of the graph into much less than n-2 complete subgraphs. But this theorem assures us that we can do no better than n-1. The resulting partitions must contain many singletons.

The other rank which we would like to know is the Boolean rank of a tournament matrix. We can treat a tournament matrix just as a bigraph when considering the biclique cover number and its bounds. For the tournament T we have the following.

$$A(T)= \begin{array}{c} x_1\\ x_2\\ x_3\\ x_4\\ x_5\\ \end{ar... ...0\\ 0&0&0&1&1\\ 1&0&0&0&0\\ 1&1&0&1&0\\ \end{array}\right]$$

Next look at the biclique covering number which is 4.

We can no look at the corresponding subgraphs of T.








This gives us a biclique covering of 4 and so bc(T)=n-1Because the maximum number of independent ones, or the biclique covering number, which we know to be less than the boolean rank of the matrix is equal to n-1 the boolean rank of M must be greater than or equal to n-1.

Another bound for the boolean rank of an n-tournament matrix M is the following. If a bipartite graph B has a set S of isolated 1's, then

$$b(A)\ge bc(B)\ge \mid S \mid$$

Look at the following adjacency matrix.

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

The bold ones give a set of four isolated one's and therefore b(A)=4since b(A) is always less than r(A). Unfortunately there is no relationship between r(A) and b(A) and this lower bound is the best we can do at the present.

Some open questions about the boolean rank of a tournament matrix Mare finding classes of tournaments whose adjacency matrices have b(M)<n-1. In general we would like to classify all tournaments where various equalities hold. In what tournament matrices can we have the following equalities?

a) $r(M)=n-1, r_{\ensuremath{\mathbb{Z^+} } }(M)=n$

b) r(M)=n-1, t(M)=n

c) $r_{\ensuremath{\mathbb{Z^+} } }(M)=n-1, t(M)=n$

Many interesting questions remain unsolved, many of which seem to be very difficult problems. There seems to be no shortage of new information to be learned about tournaments from the ranks their adjacency matrices. The same results apply to other classes of graphs, such as bipartite graphs or dominoe free-graphs. It is clearly a worthwhile area of study.