The rank of a perturbed triangular matrix

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.