5
$\begingroup$

I met a question in Bondy and Murty’s Graph theory (§1.5.13)

The adjacency matrix of a digraph $D$ is the $n \times n$ matrix $\mathbf{A}_D = (a_{uv})$, where $a_{uv}$ is the number of arcs in $D$ with tail $u$ and head $v$. Let $\mathbf{A}$ be the adjacency matrix of a tournament on $n$ vertices. Show that $\operatorname{rank}\mathbf{A}=n-1$ if $n$ is odd and $\operatorname{rank}\mathbf{A}=n$ if $n$ is even.

which I think is completely wrong. However, are there some similar conclusions related to the rank of $\mathbf{A}$? For example, when is the rank of $\mathbf{A}$ equal to $n-1$?

$\endgroup$
6
  • $\begingroup$ what makes you think it's "completely wrong"? if you know a counterexample, add it to your question $\endgroup$ Sep 21, 2022 at 10:13
  • 2
    $\begingroup$ I would think the adjacency matrix of a digraph is skew-symmetric, each edge producing a $1$ and a $-1$... $\endgroup$ Sep 21, 2022 at 12:04
  • 1
    $\begingroup$ @IlyaBogdanov That’s not how it is defined in Bondy. But yes, I suspect that the exercise was meant to apply to this skew-symmetric version of the adjacency matrix (in other words, to $\operatorname{rank}(\mathbf A-\mathbf A^t)$). $\endgroup$ Sep 21, 2022 at 12:18
  • 1
    $\begingroup$ Would you, please, define the tournament matrix? (many different definitions are possible) $\endgroup$
    – Wlod AA
    Sep 23, 2022 at 4:00
  • 1
    $\begingroup$ @WlodAA A bit late, but I added Bondy & Murty's definition of adjacency matrix of a digraph. $\endgroup$ Dec 8, 2023 at 20:23

2 Answers 2

4
$\begingroup$

The following two papers give the lower bound $n-1$ on the rank of $n\times n$ tournament matrices over fields of characteristic zero. Here a tournament matrix $M$ is a $\{0,1\}$-matrix, with zeros on the diagonal, satisfying $M+M^T=J-I$.

D. de Caen, The Ranks of Tournament Matrices, The American Mathematical Monthly, Vol. 98, No. 9 (Nov., 1991), pp. 829-83. https://doi.org/10.2307/2324270

D. de Caen and D. G. Hoffman, Impossibility of decomposing the complete graph on n points into (n - 1) isomorphic complete bipartite subgraphs, SIAM J. on Discrete Math., 2 (1989) 48-50. https://epubs.siam.org/doi/10.1137/0402005

$\endgroup$
4
$\begingroup$

Here is a proof for a $(1,-1)$-version. In other words, an antisymmetric $n\times n$ matrix with not-diagonal entries $1$ and $-1$ has rank $n$ if $n$ is even and $n-1$ if $n$ is odd.

First of all, if $n$ is odd, the rank is at most $n-1$ since antisymmetric matrix of odd order is always singular, and its principal minor of order $n-1$ is an antisymmetric matrix of even order $n-1$. This reduces the odd case to the even case, so let further $n$ be even. I claim that the rank is full even modulo 2, in other words, the determinant is odd. Indeed, if you add all other columns to the $n$-th column, it becomes (modulo 2) the all-1's column. Now adding it to the first $n-1$ columns you get a unitriangular matrix.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.