Return to Revisions

For $n=10$ there exist such a matrix of rank(4): $$ \begin{pmatrix} \phantom{-}8 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & -6 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & -2 & -2 \\ \phantom{-}18 & \phantom{-}3 & \phantom{-}3 & \phantom{-}0 & \phantom{-}6 & \phantom{-}0 & -3 & -3 & \phantom{-}0 & \phantom{-}0 \\ \phantom{-}8 & \phantom{-}0 & \phantom{-}3 & -3 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}3 & \phantom{-}1 & -2 \\ -6 & -2 & \phantom{-}0 & -2 & \phantom{-}0 & -2 & \phantom{-}0 & \phantom{-}2 & \phantom{-}0 & \phantom{-}0 \\ \phantom{-}0 & \phantom{-}0 & \phantom{-}3 & -3 & \phantom{-}6 & \phantom{-}0 & \phantom{-}0 & \phantom{-}3 & \phantom{-}3 & \phantom{-}0 \\ -7 & -1 & -1 & \phantom{-}0 & \phantom{-}1 & -1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 \\ -3 & \phantom{-}0 & -1 & \phantom{-}1 & -2 & \phantom{-}1 & \phantom{-}1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0\\ \phantom{-}9 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & -3 & -3 & -3 & -3 & \phantom{-}0 \\ \phantom{-}0 & -2 & \phantom{-}0 & -2 & \phantom{-}0 & -4 & -2 & \phantom{-}0 & -2 & \phantom{-}0 \\ \phantom{-}0 & -2 & \phantom{-}0 & -2 & -9 & \phantom{-}0 & \phantom{-}2 & \phantom{-}4 & -1 & -3 \end{pmatrix} $$ Hence we can improve our bound to $c=log_{10}(4)=0.6021$. I used the matlab code below. However I did not find any solution with $n=7$ and rank 3.

function mathoverlow_triangular

global n k n=10; k=4;

options=optimset('Display','iter');

%first run find 0-1 pattern x=fsolve(@(x) f(x,1),rand(2nk,1),options);

%second run set zeros and find nonzero entries %x=fsolve(@(x) f(x,2),x,options);

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

A=U*V'

%get 0-1 patern B=eye(n); for i=1:n-1 for j=i+1:n if max(abs(A(i,j)))<=max(abs(A(j,i))) B(j,i)=1; else B(i,j)=1; end end end

for reps=1:1e5

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

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

is=1; B1(:,ind)=B(:,ind).*randi(3,n,k).*pm;

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(:,1); end end if is B1 rank(B1) end end

% save('sol','A'); % % A % for tol=logspace(-6,-16,11) % rats(A,tol) % [N,D]=rat(A,tol) % rank(N./D) % end

end

function [y] = f(x,c)

global n k

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

UV=U*V';

y=zeros(n*(n-1)/2,1); l=1; for i=1:n-1 for j=i+1:n if c==1 y(l)=UV(i,j)*UV(j,i); else if abs(UV(i,j))<abs(UV(j,i)) y(l)=UV(i,j); else y(l)=UV(j,i); end end l=l+1; end end for i=1:n y(l)=UV(i,i)-1; l=l+1; end

if c==2 y=[y;y-min(floor(y),100);y-max(ceil(y),-100)]; end end