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

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.

• $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 8 '16 at 23:34
• Hint: Cauchy-Binet theorem. – darij grinberg Jun 9 '16 at 0:04
• 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 9 '16 at 0: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 9 '16 at 0:13
• @darijgrinberg We did not mention that theorem, sadly. I will try to think about your second advice. – Asleen Jun 9 '16 at 0:13

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.

• 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 9 '16 at 1: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
• @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

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$$.