7

Problem: We have matrix $A\in M_{n-1\times n}(\mathbb Z)$ so that the sum of elements in each row is zero. Prove that $\det(AA^T)=nk^2$, where $k\in \mathbb Z$.

What have I considered so far:

  1. First I thought, since sum of all elements in each row is zero, zero is eigenvalue of $A$ but $A\in M_{(n-1)\times n}(\mathbb Z)$ confused me.
  2. I see that $AA^T$ will be $(n-1)$ by $(n-1)$, so I tried calculating $AA^T$ but I failed to see any connection.

I did some research and found this question but we had no mention of it, which makes me believe I am on the wrong track.

Thank you all for your help.

Community
  • 1
Asleen
  • 557
  • $A$ does not have any eigenvalues at all since it is not a square matrix. If you are suspecting that $A$ has a nontrivial kernel, how should a kernel element look like? – Roland Jun 08 '16 at 23:34
  • 2
    Hint: Cauchy-Binet theorem. – darij grinberg Jun 09 '16 at 00:04
  • 2
    Hint to alternative proof: Attach a new row to the bottom of $A $; fill this row with $1$s. Call the resulting $n\times n $-matrix $B $. How does $BB^T $ compare with $AA^T $? What can you say about the determinant of $BB^T $? – darij grinberg Jun 09 '16 at 00:08
  • @Roland There will be one element all other elements are dependent of, lets say $a_{n-1}$. I will try to think more about this. – Asleen Jun 09 '16 at 00:13
  • @darijgrinberg We did not mention that theorem, sadly. I will try to think about your second advice. – Asleen Jun 09 '16 at 00:13
  • @darijgrinberg I get $det(BB^T)=n det(AA^T)$, – Asleen Jun 09 '16 at 01:27
  • @Asleen: That's good progress. But $B$ and $B^T$ are square matrices, so... – darij grinberg Jun 09 '16 at 01:49
  • @darijgrinberg Well, all I can say is that $detB detB^T = n det (AA^T)$. Now, I could assume $detB=k=detB^T$ and get $k^2 = n det (AA^T)$. If I could somehow conclude $detB=nk$, that would be great. – Asleen Jun 09 '16 at 02:01
  • Well, if an integer times $n$ is a square, then what can you say about this integer? – darij grinberg Jun 09 '16 at 02:29
  • It is the factor of a square. Product of two same integers is a square. – Asleen Jun 09 '16 at 07:42
  • Oops, my alternative proof was a fluke. Sorry for wasting your time! – darij grinberg Jun 10 '16 at 14:06

2 Answers2

5

Let $A = (B,\mathbf{b})$, where $B \in M_{n-1\times n-1}(\mathbb{Z})$ is a "left square part" of matrix $A$, i.e. $B_i^j = A_i^j$, and $\mathbf{b} \in \mathbb{Z}^{n-1}$ is a "right" part of $A$, i.e. $b_i = A_i^n$. As sum of each row is zero, we have $b_i = -\sum_{k=1}^{n-1}B_i^k$. Let $\mathbf{e}\in \mathbb{Z}^{n-1}$ be a vector with each union component, i.e. $e_i = 1$. Then $\mathbf{b} = -B\mathbf{e}$. Now we may multiply $A$ with $A^{\top}$ as block matrices: $$ AA^{\top} = (B\;\;-B\mathbf{e}) \begin{pmatrix} B^\top \\ -\mathbf{e}^\top B^\top \end{pmatrix} = BB^\top + B\mathbf{e}\mathbf{e}^\top B^\top = B(I + \mathbf{e}\mathbf{e}^\top)B^\top $$ where $I$ is identity matrix. As bouth $B$ and $I + \mathbf{e}\mathbf{e}^\top$ are square matrices we now have $$ \det(AA^\top) = \det\left(B(I + \mathbf{e}\mathbf{e}^\top)B^\top\right) = \det (B) \det(I + \mathbf{e}\mathbf{e}^\top)\det(B^\top) = \det(I + \mathbf{e}\mathbf{e}^\top)\left(\det B\right)^2. $$

$B \in M_{n-1\times n-1}(\mathbb{Z})$ thus $\det B \in \mathbb{Z}$.

Now all we need to proof is that $\det(I + \mathbf{e}\mathbf{e}^\top) = n$. This matrix (denote it with $E_{n-1}$ where $n-1$ is dimension of the space or count of raws in $E$) looks like $$ E_{n-1} = \begin{pmatrix} 2 & 1 & \dots & 1 \\ 1 & 2 & \dots & 1\\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \dots & 2 \end{pmatrix}. $$

Let $E^i_n$ be a matrix $E_n$ in which we replaced $2$ in $i$-th row with $1$. It's easy to see that $\det{E^1_n} = 1$ (using Gaussian process). Thus if $i$ is even $\det E_n^i = 1$ and if i is odd $\det E^i_n = -1$, i.e. $\det E^i_n = (-1)^i$. Now let's suppose we know that $\det E_{n-1} = n$. We may decompose $\det E_n$ using Laplace expansion: $$ \det E_n = 2\det E_{n-1} + \sum_{i=1}^{n-1} (-1)^{i}\det E^i_{n-1} = 2n - (n-1) = n+1. $$ QED.

darij grinberg
  • 17,777
Anton Grudkin
  • 2,955
  • 2
    Another way to prove that the last determinant is $n$ is from its eigenvalues: it has $1$ as an eigenvalue with multiplicity $n-2$, and $n$ as an eigenvalue with multiplicity 1. – Semiclassical Jun 09 '16 at 01:03
  • @Semiclassical I understand why is $n$ an eigenvalue. Could you please explain why is $1$ an eigenvalue with multiplicity $n-2$? Thank you! – Asleen Jun 11 '16 at 21:42
  • 1
    @Asleen Well, $(1,-1,0,\cdots)^T$ is such an eigenvector, and you can work out $n-1$ other examples which are all linearly independent. (More heuristically, note that subtracting $1I$ from $E_{n-1}$ gives a matrix which has multiple rows identical. That signals that $1$ will be an eigenvalue of multiplicity bigger than one.) – Semiclassical Jun 11 '16 at 21:53
1

Rather than partitioning $A$ as in the other answer, we may let a row vector and $A$ adjoin instead. Let $e=(1,\ldots,1)^T\in\mathbb R^n$. Then \begin{align} &\pmatrix{e^T\\ A}\left(\begin{array}{c|c}e&\begin{array}{c}0\\ \hline I_{n-1}\end{array}\end{array}\right)=\pmatrix{n&\ast\\ 0&\ast},\tag{1}\\ &\pmatrix{e^T\\ A}\pmatrix{e&A^T}=\pmatrix{n&0\\ 0&AA^T},\tag{2} \end{align} where the RHS of $(1)$ is an integer matrix. It follows from $(1)$ that $\det\pmatrix{e^T\\ A}=nk$ for some integer $k$, and from $(2)$ that $(nk)^2=n\det(AA^T)$. Thus $\det(AA^T)=nk^2$.

user1551
  • 139,064