4

Suppose $A$ is a $n \times n$ matrix with $0-1$ entries. Prove that the determinant of $X = nJ+B+B^*+2AA^T$ is divisible by $2^{n-1}$ where $B=(i-1)AJ$ and $J$ is the all ones matrix.

I've reduced a tricky tournament problem to this simpler problem, but I'm not sure how to proceed. The biggest observation so far is that $X$ is Hermitian because it is the sum of $3$ Hermitian matrices. A hint rather than a full answer would be fine since I'm trying to do as much of this problem by myself as possible.

Edit: I forgot one detail. Why is the determinant non-negative?

Display name
  • 5,144
  • Both $nJ + B = \left(n+\left(i-1\right)A\right)J$ and $B^\ast = JA^T$ are matrices of rank $\leq 1$ (since $J$ has rank $\leq 1$). So you get $X$ by two consecutive rank-$1$ updates applied to the matrix $2AA^T$. The matrix determinant lemma gives you a way to track a determinant through rank-$1$ updates, though in the end you'll need not just the determinant of $2AA^T$ but also its $\left(n-1\right)\times\left(n-1\right)$-minors and its $\left(n-2\right)\times\left(n-2\right)$-minors. ... – darij grinberg Jan 15 '20 at 18:58
  • ... Now, both the determinant and the $\left(n-1\right)\times\left(n-1\right)$-minors of $2AA^T$ are divisible by $2^{n-1}$, since all entries of $2AA^T$ are divisible by $2$. It remains to check the $\left(n-2\right)\times\left(n-2\right)$-minors, which may be more complicated. – darij grinberg Jan 15 '20 at 18:58
  • (Note: I am using the easy fact that a divisibility $u \mid v$ between two integers $u, v$ holds in the ring $\mathbb{Z}\left[i\right]$ of Gaussian integers if and only if it holds in the ring $\mathbb{Z}$ of integers. This allows me to work with non-integer matrices such as $nJ + B$ and $B^\ast$.) – darij grinberg Jan 15 '20 at 19:00
  • Ah, easier argument: Subtract the first row of $X$ from each of the other rows. Let $Y$ be the resulting matrix. Then, subtract the first column of $Y$ from each of the other columns. Let $Z$ be the resulting matrix. This $Z$ has the following properties: (1) All entries except those in the first row and those in the first column are multiples of $2$. Furthermore: (2) All entries in the first row but not in the first column are multiples of $i-1$. (Or maybe $-i-1$.) Finally: (3) All entries in the first column but not in the first row are multiples of $-i-1$. (Or maybe $i-1$.) Now, ... – darij grinberg Jan 15 '20 at 19:08
  • ... I claim that properties (1), (2) and (3) together entail that every addend in the Leibniz formula for $\det Z$ is a multiple of $2^{n-1}$. (This relies on $\left(i-1\right)\left(-i-1\right) = 2$.) Thus, so is $\det Z$. But $\det Z = \det Y = \det X$. – darij grinberg Jan 15 '20 at 19:09
  • @darijgrinberg Your row reduction approach works. This isn't the first time that I've gotten very close to a solution and then missed the idea of row reducing. Coming back to this question, I forgot one detail. How do I show the determinant is non-negative? – Display name Jan 24 '20 at 03:24
  • Not sure. Have you tried showing that it is positive semidefinite? – darij grinberg Jan 24 '20 at 09:42

0 Answers0