Rank of a matrix with $a_{ii}=0$ and $a_{ij}+a_{ji}=1$

Question

Let $A=(a_{ij})$ and an $n\times n$ real matrix such that $$a_{ii}=0~(1\le i\le n),\quad a_{ij}+a_{ji}=1~(1\le i<j\le n).$$ Then prove that ${\rm rank}(A)\ge n-1 $.

This is a problem I saw in an exercise book. It is clear that $A+A^{\rm T}$ is a matrix with all diagonal entries $0$ and off-diagonal entries $1$. Can we get the ${\rm rank}(A)$ from it? Or how can we prove it in other ways? Thanks.

Answer 1

Claim: If a real matrix $A$ satisfies $ A + A^T + kI = J$, where $J$ is the all ones matrix and $k\neq 0$ is a constant, then the rank of $A$ is $\geq n-1$.

Corollary: Applying this to the problem at hand, with $k = 1$, we get that the matrix $A$ has rank at least $n-1$. Equality is possible, like if the first (any) column is all 0's.

Proof of claim: Observe that

• $J$ has eigenvalues of $ \{ n, 0, 0, \ldots, 0 \}$.
• So $A + A^T$ has eigenvalues of $ \{ n-k, -k, -k, \ldots, -k \}$. Pick a orthogonal basis for the eigenspaces.
• Do the corresponding change of basis, so that $A = [b_{ij}]$ with $b_{11} = n-k, b_{ii} = -k, $ for $i\neq 1$ and $b_{ij} = - b_{ji}$ for $i \neq j$.
• Consider the sub matrix of $a_{11}$ (removing the first row and column), which is of the form $ M= -k I_{n-1} + S$ where $S$ is a skew-symmetric matrix.
• Since the eigenvalues of $S$ are of the form $e_j \sqrt{-1}$ (where $e_j$ are real numbers, possibly 0), so the eigenvalues of $M$ are of the form $ -k + e_j \sqrt{-1}$. In particular, since $k \neq 0$, these eigenvalues are never 0, so $M$ has full rank.
• Thus the rank of $A$ is at least $n-1$.

Answer 2

By condition, $A$ satisfies $A + A^\top = ee^\top - I_{(n)}$, where $e$ is an $n$-long vector of all ones. View $A + A^\top$ as a linear operator on the real linear space $V := \mathbb{R}^n$, and let $U$ be the subspace of $V$ spanned by $e$. It then follows that for any $x \in U^\perp$, we have \begin{align} 2x^\top A x = x^\top(A + A^\top)x = x^\top ee^\top x-x^\top x = -x^\top x \leq 0. \tag{1}\label{1} \end{align} Moreover, $\eqref{1}$ shows that $x^\top A x < 0$ for $x \in U^\perp$ and $x \neq 0$. Let's prove that this implication necessitates $\operatorname{rank}(A) \geq n - 1$.

If $\operatorname{rank}(A) = r < n - 1$, then the dimensionality of the null subspace $W := \{x \in V: Ax = 0\}$ is $n - r$, which is greater than $n - (n - 1) = 1$. The non-positive condition derived above clearly implies that $U^\perp \cap W = \{0\}$. It then follows by the dimensionality theorem that \begin{align} \dim(U^\perp + W) = \dim(U^\perp) + \dim(W) = n - 1 + n - r > n - 1 + 1 = n, \end{align} which is impossible because $U^\perp + W$ is a subspace of $V$, whose dimensionality is $n$. This completes the proof.