19
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Max Alekseyev May 13 '17 at 23:54
  • $\begingroup$ 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 $\endgroup$ – user35593 May 30 '17 at 7:34
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Erm... The second $B$ should be $C$, right? $\endgroup$ – fedja Nov 16 '17 at 19:39
  • $\begingroup$ 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/…. $\endgroup$ – Seva Nov 16 '17 at 22:34
10
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Seva May 19 '17 at 5:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Markus Sprecher May 19 '17 at 6:02
  • $\begingroup$ 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. $\endgroup$ – Seva Jun 1 '17 at 5:53
  • $\begingroup$ I agree with you and tried to simplify the matrix as much as possible. (However without permutations.) $\endgroup$ – Markus Sprecher Jun 1 '17 at 19:39
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Yoav Kallus Jun 2 '17 at 19:21
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Fedor Petrov Jun 27 '17 at 11:31
  • $\begingroup$ (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? $\endgroup$ – Fedor Petrov Jun 27 '17 at 11:31
  • $\begingroup$ @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). $\endgroup$ – Seva Jun 27 '17 at 12:45
2
$\begingroup$

The picture below shows a solution with rank 5 and $n=15$. Solution for $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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.