Skip to main content
3 of 3
Rollback to Revision 1 - Edit approval overridden by post owner or moderator
Seva
  • 23k
  • 2
  • 59
  • 141

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.

Seva
  • 23k
  • 2
  • 59
  • 141