# The rank of a perturbed triangular matrix

$\DeclareMathOperator{\rk}{rk}$

The question below is implicit in this MO post, but I believe it deserves to be asked explicitly, particularly now that I have some more numerical evidence.

Suppose that $A$ is a real, square matrix of order $n$, such that all main-diagonal elements of $A$ are distinct from $0$, and of any two elements symmetric about the main diagonal, at least one is equal to $0$. That is, writing $A=(a_{ij})_{1\le i,j\le n}$, we have $a_{ii}\ne 0$ and $a_{ij}a_{ji}=0$ whenever $i,j\in[1,n]$, $i\ne j$. In other words, $A$ can be obtained from a non-singular triangular matrix by switching some pairs of symmetric elements. How small can the rank of such a matrix be, in terms of $n$?

Since the pointwise product $A\circ A^t$ is full-rank, as an immediate corollary of the inequality $\rk(B\circ C)\le\rk(B)\,\rk(C)$ we have $\rk(A)\ge\sqrt n$. How sharp this estimate is? Is it true that $\liminf_{n\to\infty} \log(\rk(A))/\log(n)=\frac12$?

Computations show that there are matrices of order $6$ and rank $3$ satisfying the assumptions above; taking $A$ to be a tensor power of such a matrix, we will have $\rk(A)=n^c$ with $=\log_6(3)\approx0.6131$.

I do not know whether there exist matrices of order $7$ and rank $3$ with the property in question.

• It may be worth to notice that $A+A^T$ is a symmetric matrix, and $\rk(A)\geq \frac{1}{2}\rk(A+A^T)$. – Max Alekseyev May 13 '17 at 23:54
• Writing A=UV' with U,V in R^(n×k) and interpring the rows of U as linear forms and the rows of V as vectors. Then the question is equivalent of asking if there exists n hyperplanes in R^k a1,...,an and n points v1,...,vn in R^k such that vi is not on ai for all i and vi is on aj or vj on ai for any pair (i,j). I.e. we have a incidence graph problem. The following article might therefore be interesting sciencedirect.com/science/article/pii/S092577210200127X – user35593 May 30 '17 at 7:34

$\DeclareMathOperator{\rk}{rk}$It is possible to construct a matrix with $\rk(A)\leq 2\sqrt{n}$. Assuming that $n=r^2$ with an integer $r$, introduce two matrices $B$ and $C$, whose rows and columns are indexed by elements of $\{1,2,\dotsc,r\}^2$, and whose entries are defined by $$B_{(x,y),(x',y')}=\begin{cases}1&\text{if }x=x',\\0&\text{otherwise},\end{cases}$$ and $$C_{(x,y),(x',y')}=\begin{cases}-1&\text{if }y<y',\\0&\text{otherwise},\end{cases}$$ where $(x,y),(x',y')\in \{1,2,\dotsc,r\}^2$.

We have $\rk(B)\leq r$ and $\rk(C)\leq r$, and $A:=B+C$ is an $r^2$-by-$r^2$ matrix satisfying the requisite condition.

This is a minor modification of the constructions that I used in a paper of mine.

• Erm... The second $B$ should be $C$, right? – fedja Nov 16 '17 at 19:39
• Great solution! It can also be presented using the tensor product: $$A = I_r\otimes J_r-J_r\otimes T_r,$$ where $I_r$ is the identity matrix of order $r$, $J_r$ is the all-$1$ matrix of order $r$, and $T_r$ is the matrix of order $r$ with all entries on or below the main diagonal equal to $0$, and all entries above the main diagonal equal to $1$. I wonder whether anything of this sort can be used in this problem: mathoverflow.net/questions/266531/…. – Seva Nov 16 '17 at 22:34

For $n=10$ there exists such a matrix of rank(4) (see below).

Hence we can improve the upper bound to $c=\log_{10}(4)=0.6021$. I found this matrix using matlab. However I did not find any solution with $n=7$ and rank 3.

To answer the question in the comments: Yes there exist solutions with only $-1,0$ and $1$:

$$\begin{pmatrix} \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}1\\ \phantom{-}0 & \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}0 & \phantom{-}1 & \phantom{-}0\\ -1 & \phantom{-}0 & \phantom{-}1 & \phantom{-}0 & -1 & \phantom{-}0 & \phantom{-}1 & -1 & \phantom{-}1 & \phantom{-}0\\ \phantom{-}0 & \phantom{-}1 & \phantom{-}1 & -1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & -1\\ \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0\\ \phantom{-}1 & \phantom{-}0 & -1 & \phantom{-}1 & \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0\\ \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0 & -1\\ \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & -1 & -1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}1\\ \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}0 & \phantom{-}1 & \phantom{-}1 & -1 & \phantom{-}1 & \phantom{-}0\\ \phantom{-}0 & \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & -1 & -1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}1 \end{pmatrix}$$

Here is the matlab code I used:

function mathoverlow_triangular

global n k nk
n=10;
k=4;
nk=n*k;

options=optimset('Jacobian','on');%'Display','iter',,'DerivativeCheck','on'

exitflag=0;

while exitflag~=1 %until a solution has been found

[x,~,exitflag]=fsolve(@(x) f(x),rand(2*nk,1),options);

end

[~,~,A]=f(x)

%find 0-1 pattern
nz=double(abs(A)>=abs(A'));
save('sol','nz');

for reps=1:1e4 %try this many times finding an integer solution

p=randperm(n);
ind=p(1:k);

B1=nz;
pm=1-2*(rand(n,k)>.5);

is=1;
B1(:,ind)=nz(:,ind).*pm;%.*randi(4,n,k)

for j=k+1:n
nu=null(B1(B1(:,p(j))==0,ind),'r');
%exclude those which give 0 on diagonal
if size(nu,2)>0
nu=nu(:,B1(p(j),ind)*nu~=0);
end
if size(nu,2)==0
is=0;
break;
else
B1(:,p(j))=B1(:,ind)*nu(:,randi(size(nu,2)));
end
end
if is
A=B1;
[N,D]=rat(A);
A=round(A.*(ones(n,1)*lcm_array(D)));
A=round(A./(ones(n,1)*gcd_array(A)));
A=round(A./(gcd_array(A')'*ones(1,n)));
if max(abs(A(:)))==1
%write tex code
for i=1:n
stri='';
for j=1:n-1
stri=[stri num2str(A(i,j)) ' & '];
end
disp([stri num2str(A(i,end)) '\\']);
end
disp('');
save('sol','A');
end
end
end

end

function [b]=lcm_array(A)

if size(A,1)==1
b=A;
else
b=lcm(lcm_array(A(1:end-1,:)),A(end,:));
end

end

function [b]=gcd_array(A)

if size(A,1)==1
b=A;
else
b=gcd(gcd_array(A(1:end-1,:)),A(end,:));
end

end

function [res,J,UV] = f(x)

global n k nk
U=reshape(x(1:nk),[n k]);
V=reshape(x(nk+1:end),[n k]);

UV=U*V';
Tnk=transposeT(n,k);
res=UV'.*UV-eye(n);
Tnn=transposeT(n,n);
n2=n^2;
dUV=sparse(1:n2,1:n2,UV(:),n2,n2);
UVt=UV';
dUVt=sparse(1:n2,1:n2,UVt(:),n2,n2);
J=(dUVt+dUV*Tnn)*[kron(V,speye(n)) kron(speye(n),U)*Tnk];

end

function T = transposeT(n,k)
%derivative of transpose map
nk=n*k;
u=reshape(1:nk,[n k]);
v=u';
T=sparse(u(:),v(:),ones(nk,1),nk,nk);

end

• Interesting! This suggests that the lower bound ${\rm rk}\,A\ge\sqrt n$ may be sharp. How did you find this example? I assume you have not checked all matrices with the entries not exceeding 10, say? Are there examples of order $10$ and rank $4$ with all elements in $\{-1,0,1\}$? A very interesting observation is that in your example, as well as in all examples that I found, there is no pair of indices $i,j$ with $a_{ij}=a_{ji}=0$. One last remark is that your example can be slightly simplified by factoring out the common factors from some rows. – Seva May 19 '17 at 5:37
• I parametrized the matrix as $U*V'$ with $U,V\in \mathbb{R}^{n\times r}$ and solved the corresponding system of nonlinear equations. When I had a numerical solution I tried to find integer solutions with the same 0-1 patterns. For this I filled $r$ columns randomly with integers $(-3,..,3)$ and tested if it can be completed to a solution. After a lot of repetions the example above appeared. – Markus Sprecher May 19 '17 at 6:02
• It is interesting to see a $\{0,\pm1\}$-solution. This makes me wonder whether there always exists a smallest-possible-rank matrix with all entries in $\{0,\pm1\}$. Another remark is that there are lots of matrices which can be obtained from your matrix by switching the signs of some rows / columns and permuting them (in a coordinated way). It would be extremely interesting to find some "nice" matrix among them, in the hope to grasp and generalize the idea. – Seva Jun 1 '17 at 5:53
• I agree with you and tried to simplify the matrix as much as possible. (However without permutations.) – Markus Sprecher Jun 1 '17 at 19:39
• Here is a nice-looking permutation. It's easy to generalize the top 9x9 block to a 3nx3n matrix of rank n+1 with the desired property. It's not immediately obvious to me how the last row and column work. $\begin{array}{cccccccccc}1&0&0&1&0&1&1&0&0&1\\ 0&1&1&0&1&0&-1&0&0&0\\ 1&0&1&0&0&1&0&1&0&0\\ 0&1&0&1&1&0&0&-1&0&1\\ 1&0&1&0&1&0&0&0&1&1\\ 0&1&0&1&0&1&0&0&-1&0\\ 0&0&-1&1&-1&1&1&0&-1&0\\ 1&-1&0&0&-1&1&1&1&0&0\\ 1&-1&1&-1&0&0&0&1&1&0\\ 0&-1&-1&0&0&-1&1&-1&1&1\end{array}$ – Yoav Kallus Jun 2 '17 at 19:21

This is not quite a solution of the original problem, but rather of a related and, perhaps, even more natural one:

How small can the ranks of real matrices $B=(b_{ij})_{1\le i,j\le n}$ and $C=(c_{ij})_{1\le i,j\le n}$ be, given that $b_{ii}c_{ii}\ne 0$, while $b_{ij}c_{ji}=0$ whenever $i\ne j$?

The inequality $\rk(B\circ C)\le\rk(B)\rk(C)$ gives

$$\rk(B)\rk(C)\ge n,$$

and I claim that this estimate is sharp. To see this, associate the rows and columns of our matrices with the elements of a finite abelian group $G$ of order $|G|=n$, consider a direct sum decomposition $G=G_1\oplus G_2$ and, denoting by $I_1$ and $I_2$ the indicator functions $G_1$ and $G_2$, respectively, for $u,v\in G$ let $b_{uv}:=I_1(u-v)$ and $c_{uv}:=I_2(u-v)$. We have then $b_{uv}c_{vu}\ne 0$ if and only if $u-v\in G_1$ and $v-u\in G_2$, which is equivalent to $u=v$. On the other hand, each row of $B$ is then identical to $|G_1|$ other rows, showing that $\rk(B)\le|G|/|G_1|=|G_2|$ and, similarly, $\rk(C)\le|G_1|$.

Thus, for instance, for $n=9$, taking $G=\mathbb Z_3^2$, the matrices may look as follows: $$B=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}, \quad C=\begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}.$$

I still wonder whether it is possible to modify somehow the construction to have $B=C$ and $\rk(B)=\rk(C)\approx\sqrt n$.

• Restrict the initial question to circulant matrices in some (additive, by the way why? Non-abelian groups also look ok) group $G$: $b_{ij}=f(i-j)$, the condition becomes $f(0)\ne 0$, $f(x)f(-x)=0$ for $x\ne 0$. We want the small rank. What is the rank of a circulant matrix? It equals to the number of characters $\chi$ satisfying $\chi(\sum_{g\in G} f(g)g)\ne 0$. (to be continued) – Fedor Petrov Jun 27 '17 at 11:31
• (continuation) Say, for the cyclic group of order $n$, we need a polynomial $P(x)=c_0+c_1x+\dots+c_{n-1}x^{n-1}$ satisfying $c_0\ne 0$, $c_kc_{n-k}=0$ for $k=1,\dots,n-1$ and satisfying $P(x)=0$ for almost all (say, all but about $\sqrt{n}$ different $x$) $n$-roots of unity. Is this possible? – Fedor Petrov Jun 27 '17 at 11:31
• @FedorPetrov: I thought about the circulant matrices in connection with this problem, without getting anywhere (which does not mean, of course, that this is a wrong direction). – Seva Jun 27 '17 at 12:45

The picture below shows a solution with rank 5 and $n=15$. Each of the 9 5×5 subblocks are cyclic. The construction might be generalizable. This would mean that for any odd r there is such a matrix of size $r (r-1)/2$ with rank $r$. This would prove that the bound given by the OP is sharp.

• row 6 to row 15 are always a sum of two rows from row 1 to row 5. – user100927 May 22 '17 at 16:29
• Sorry, I made a mistake! The matrix above does not have rank 5 I think. I will try to fix this. – user35593 May 24 '17 at 20:14
• It seema that it can not be fixed – user35593 May 30 '17 at 3:09