Kernel of a zero diagonal, non-negative symmetric matrix

linear algebramatrices

Let $A\in M^n(\mathbb{R})$ a symmetric matrix with zero principal diagonal and with strictly positive off-diagonal entries.

What is the highest possible dimension of $\,\mathbf{Ker(A)}$?

When $n=2,3$ it turns out that $A$ is invertible.

If $n=4$ then $A$ can be singular, with $dim(Ker(A))=1$.

I would like to understand if there is a method to study the case of a generic $n$. Thank you for any suggestion.

Best Answer

The maximum possible nullity $d_n$ is given by $(d_1,d_2,d_3)=(1,0,0)$ (which is evident if you consider $\det(A)$) and $d_n=n-3$ when $n\ge4$.

When $n\ge4$, since the leading principal $3\times3$ submatrix of $A$ is non-singular, it is obvious that $d_n\le n-3$. So, it suffices to construct a feasible $n\times n$ matrix $A_n$ of nullity $n-3$.

In our construction, $A_n$ will be an integer matrix and its leading principal $3\times3$ submatrix is $$ Z=\pmatrix{0&1&1\\ 1&0&1\\ 1&1&0}. $$ Since $Z$ is non-singular, if we are able to construct an $A_n$ of nullity $n-3$, then the fourth up to the last rows/columns of $A_n$ must be linear combinations of the first three. Consequently, for every $3\le k\le n$, the leading principal $k\times k$ submatrix of $A_n$ is automatically a feasible matrix of size $k$.

It follows that we only need to construct $A_n$ for each $n$ of the form $3m\ge6$. Examples for $n=3m-1$ or $n=3m-2$ can be obtained by deleting rows and columns from $A_{3m}$.

Here is our construction. Let $n=3m\ge6$. By diagonalising $Z$ via congruence over $\mathbb Q$, we see that $Z$ is congruent to $D=\operatorname{diag}(-2,-2,2)$ via an integer matrix: $$ P=\pmatrix{1&-1&1\\ -1&-1&1\\ 0&1&0},\ P^TZP=D, \ ZP=\pmatrix{-1&0&1\\ 1&0&1\\ 0&-2&2}.\tag{$\ast$} $$ Let $t_1,t_2,\ldots,t_{n-3}>1$ be any $n-3$ distinct positive integers and $v_i=(t_i^2-1,\ 2t_i)^T\in\mathbb Z^2$. Note that $v_i>0$ (because $t_i>1$) and $\|v_i\|=t_i^2+1$ is an integer. This is not surprising, becuase $v_i$ is actually constructed from Euclid's formula for generating Pythagorean triples. We now define \begin{aligned} B&=P\pmatrix{v_1&\cdots&v_{n-3}\\ \|v_1\|&\cdots&\|v_{n-3}\|} \in \mathbb Z^{3\times(n-3)},\\ A_n&=\pmatrix{I_3\\ B^T}Z\pmatrix{I_3&B}=\pmatrix{Z&ZB\\ B^TZ&B^TZB} \in \mathbb Z^{n\times n}. \end{aligned} By construction, $A_n$ always has rank $3$ and hence its nullity is $n-3$. The only question is whether or not $A_n$ has a zero diagonal and positive off-diagonal entries. Let us partition $B$ into $\pmatrix{B_1&\cdots&B_m}$, where each $B_k$ is a square integer matrix of size $3$. Thus we need to show that

  1. $B_k^TZB_k$ has the sign pattern of $Z$,
  2. $B_k^TZB_l$ is entrywise positive whenever $k\ne l$, and
  3. $ZB_l$ is entrywise positive.

It suffices to consider only the case $k=1$ and $l=2$, as all other cases are completely parallel to this one. Since $P^TZP=\operatorname{diag}(-2,-2,2)$ and $ZP$ is given by $(\ast)$, the three conditions above are equivalent to

  1. $-\langle v_i,v_i\rangle+\|v_i\|^2=0$ (which is obviously true) and $\|v_i\|\|v_j\|-\langle v_i,v_j\rangle>0$ (which is Cauchy-Schwarz inequality) when $i,j\in\{1,2,3\}$ and $i\ne j$,
  2. $-\langle v_i,v_j\rangle+\|v_i\|\|v_j\|>0$ (Cauchy-Schwarz inequality again) when $i\in\{1,2,3\},\ j\in\{4,5,6\}$.
  3. $-(t_i^2-1)+\|v_i\|>0,\ -2t_i+\|v_i\|>0$ and $(t_i^2-1)+\|v_i\|>0$ (which are true because $t_i^2-1$ and $2t_i$ are two positive coordinates of $v_i$) for each $i\in\{1,2,3,4,5,6\}$.

The two Cauchy-Schwarz inequalities above are strict because by construction, no two $v_i$s are parallel to each other. Thus all conditions are satisfied and our proof is complete.

Here is a Matlab/Octave script that you may use for generating an integer matrix $A_n$:

n=9; % or any n=3m >= 6

P=[1 -1 1;-1 -1 1;0 1 0];
Z=ones(3,3)-eye(3);
t=2:(n-2);  % any n-3 distinct positive integers > 1 will do
B=P*[t.^2-1;2*t;t.^2+1];  % note: one may further divide B by 2
                          % to get an even nicer form of A,
                          % but don't do this here
A=[Z Z*B; B'*Z B'*Z*B]

% verify that
%   A has a zero diagonal
%   A has positive off-diagonal entries
[max(abs(diag(A))), min(min(A+eye(n)))]
% the result should be [0, some positive integer]

% verify that A_n has n-3 zero eigenvalues
sort(abs(eig(A)))  % all except the last 3 entries
                   % should be close to machine epsilon
rank(A)  % should be 3 in the absence of numerical errors

E.g. $$ A_9=\pmatrix{ 0& 1& 1& 2& 2& 2& 2& 2& 2\\ 1& 0& 1& 8&18&32&50&72&98\\ 1& 1& 0& 2& 8&18&32&50&72\\ 2& 8& 2& 0& 4&16&36&64&100\\ 2&18& 8& 4& 0& 4&16&36&64\\ 2&32&18&16& 4& 0& 4&16&36\\ 2&50&32&36&16& 4& 0& 4&16\\ 2&72&50&64&36&16& 4& 0& 4\\ 2&98&72&100&64&36&16& 4& 0 }. $$ It happens that with our choices of $t_i\ (=i+1)$ in the Matlab code, all entries of $ZB$ are even. So, if we replace $B$ by $\frac12 B$ in the definition of $A_n$, the outcome will appear nicer and a clear pattern emerges: $$ A_9=\pmatrix{ 0& 1& 1& 1& 1& 1& 1& 1& 1\\ 1& 0& 1& 4& 9&16&25&36&49\\ 1& 1& 0& 1& 4& 9&16&25&36\\ 1& 4& 1& 0& 1& 4& 9&16&25\\ 1& 9& 4& 1& 0& 1& 4& 9&16\\ 1&16& 9& 4& 1& 0& 1& 4& 9\\ 1&25&16& 9& 4& 1& 0& 1& 4\\ 1&36&25&16& 9& 4& 1& 0& 1\\ 1&49&36&25&16& 9& 4& 1& 0 }, $$ and the new $B$ (after division by $2$) in this example is $$ B=\pmatrix{ 2& 6&12&20&30&42\\ -1&-2&-3&-4&-5&-6\\ 2& 3& 4& 5& 6& 7}. $$

Edit. One becomes more absent-minded when growing old. It turned out that I have met a matrix of this kind before and proved that the matrix always has rank $3$! See Prove a $n \times n $ matrix has rank 3 .

Related Question