Return to Answer

A modest start, but before doing so, one suggestion: I would index the columns and rows from $0$ to $n-1$, so $a_{ij} = (-1)^{\lfloor 2ij/n\rfloor}$.

We prove that the conjectured value of $\operatorname{rank}(A_n)$ is an upper bound. For $1\le k\le n-1$ let $v_k$ be the row vector with $1$ in positions $k$ and $n-k$ and $0$ elsewhere, and for $0\le j\le n-1$ let $a_j$ be the $j$'th column of $A_n$.

As $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity for $1\le j, k\le n-1$ if and only if $n$ does not divide $2kj$, we obtain \begin{equation} v_ka_j= \begin{cases} 0 & \text{if }n\nmid 2kj\\ 2\cdot(-1)^{2kj/n} & \text{if }n\mid 2kj. \end{cases} \end{equation} Set $d=\operatorname{gcd}(n, k)$ and assume that $k$ does not divide $n$, hence $d<k$. We claim that $w_k=v_k-v_d$ is a left eigenvector of $A_n$. We consider two cases:

• If $n$ does not divide $2kj$, then $n$ does not divide $2dj$ either. So $w_ka_j=v_ka_j-v_da_j=0-0=0$.
• Now suppose that $n$ divides $2kj$. Then $n/d$ divides $2jk/d$, and since $n/d$ and $k/d$ are relatively prime, we get that $n/d$ divides $2j$, so $n\mid 2dj$. So $w_ka_j=0$ once we know that $2kj/n$ and $2dj/n$ have the same parity. As $d\mid k$, this could only fail if $k/d$ were even while $2dj/n$ were odd. This would imply $2d\mid k$ and $2d\mid n$, respectively, contrary to the choice of $d$.

Thus $w_k$ is an eigenvector of $A_n$ for $1\le k<n/2$ if $k\nmid n$, and these vectors are linearly independent.

A modest start, but before doing so, one suggestion: I would index the columns and rows from $0$ to $n-1$, so $a_{ij} = (-1)^{\lfloor 2ij/n\rfloor}$.

We prove that the conjectured value of $\operatorname{rank}(A_n)$ is an upper bound. For $1\le k\le n-1$ let $v_k$ be the row vector with $1$ in positions $k$ and $n-k$ and $0$ elsewhere, and for $0\le j\le n-1$ let $a_j$ be the $j$'th column of $A_n$.

As $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity if and only if $n$ does not divide $2kj$, we obtain \begin{equation} v_ka_j= \begin{cases} 0 & \text{if }n\nmid 2kj\\ 2\cdot(-1)^{2kj/n} & \text{if }n\mid 2kj. \end{cases} \end{equation} Set $d=\operatorname{gcd}(n, k)$ and assume that $k$ does not divide $n$, hence $d<k$. We claim that $w_k=v_k-v_d$ is a left eigenvector of $A_n$. We consider two cases:

• If $n$ does not divide $2kj$, then $n$ does not divide $2dj$ either. So $w_ka_j=v_ka_j-v_da_j=0-0=0$.
• Now suppose that $n$ divides $2kj$. Then $n/d$ divides $2jk/d$, and since $n/d$ and $k/d$ are relatively prime, we get that $n/d$ divides $2j$, so $n\mid 2dj$. So $w_ka_j=0$ once we know that $2kj/n$ and $2dj/n$ have the same parity. As $d\mid k$, this could only fail if $k/d$ were even while $2dj/n$ were odd. This would imply $2d\mid k$ and $2d\mid n$, respectively, contrary to the choice of $d$.

Thus $w_k$ is an eigenvector of $A_n$ for $1\le k<n/2$ if $k\nmid n$, and these vectors are linearly independent.

A modest start, but before doing so, one suggestion: I would index the columns and rows from $0$ to $n-1$, so $a_{ij} = (-1)^{\lfloor 2ij/n\rfloor}$.

Let $n=2m+1$ be an odd prime. Then $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity for $1\le j, k\le n-1$.

Let $v_k$ be the row vector with $1$ in positions $k$ and $n-k$ and $0$ elsewhere. Thus $v_k$ is a left eigenvector for $1\le k\le n-1$ of $A_n'$ where $A_n'$ is the matrix $A_n$ with the first column removed. As the first column of $A_n$ is constantly $1$, the vectors $v_k-v_m$ for $1\le k\le m-1$ are left eigenvectors of $A_n$. And clearly they are linearly independent.

Thus for $n$ an odd prime, we get $\operatorname{rank}(A_n)\le\lfloor(n+3)/2\rfloor$.

The argument generalizes to give the upper bound of the rank for arbitrary $n$. For simplicity I assume that $n$ is odd. The even case is slightly more involved. Let $v_k$ be as above, and let $a_j$ be the $j$'th column of $A_n$. Since $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity if and only if $n$ does not divide $2kj$, we get $v_ka_j=0$ if $n\nmid 2kj$, and $v_ka_j=2$ otherwise.

Set $d=\operatorname{gcd}(n, k)$. If $k$ does not divide $n$, then $d<k$. Furthermore, $n$ divides $2kj$ if and only if $n$ divides $2(k-d)j$. Thus $v_k-v_{k-d}$ is an eigenvector of $A_n$ for each $k$ which does not divide $n$. If we restrict to $1\le k\le m=(n-1)/2$ again, and note that each proper divisor of $n$ is in this range, we see that we got the right number of linearly independent vectors.

A modest start, but before doing so, one suggestion: I would index the columns and rows from $0$ to $n-1$, so $a_{ij} = (-1)^{\lfloor 2ij/n\rfloor}$.

We prove that the conjectured value of $\operatorname{rank}(A_n)$ is an upper bound. For $1\le k\le n-1$ let $v_k$ be the row vector with $1$ in positions $k$ and $n-k$ and $0$ elsewhere, and for $0\le j\le n-1$ let $a_j$ be the $j$'th column of $A_n$.

As $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity for $1\le j, k\le n-1$ if and only if $n$ does not divide $2kj$, we obtain \begin{equation} v_ka_j= \begin{cases} 0 & \text{if }n\nmid 2kj\\ 2\cdot(-1)^{2kj/n} & \text{if }n\mid 2kj. \end{cases} \end{equation} Set $d=\operatorname{gcd}(n, k)$ and assume that $k$ does not divide $n$, hence $d<k$. We claim that $w_k=v_k-v_d$ is a left eigenvector of $A_n$. We consider two cases:

• If $n$ does not divide $2kj$, then $n$ does not divide $2dj$ either. So $w_ka_j=v_ka_j-v_da_j=0-0=0$.
• Now suppose that $n$ divides $2kj$. Then $n/d$ divides $2jk/d$, and since $n/d$ and $k/d$ are relatively prime, we get that $n/d$ divides $2j$, so $n\mid 2dj$. So $w_ka_j=0$ once we know that $2kj/n$ and $2dj/n$ have the same parity. As $d\mid k$, this could only fail if $k/d$ were even while $2dj/n$ were odd. This would imply $2d\mid k$ and $2d\mid n$, respectively, contrary to the choice of $d$.

Thus $w_k$ is an eigenvector of $A_n$ for $1\le k<n/2$ if $k\nmid n$, and these vectors are linearly independent.

A modest start, but before doing so, one suggestion: I would index the columns and rows from $0$ to $n-1$, so $a_{ij} = (-1)^{\lfloor 2ij/n\rfloor}$.

Let $n=2m+1$ be an odd prime. Then $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity for $1\le j, k\le n-1$.

Let $v_k$ be the row vector with $1$ in positions $k$ and $n-k$ and $0$ elsewhere. Thus $v_k$ is a left eigenvector for $1\le k\le n-1$ of $A_n'$ where $A_n'$ is the matrix $A_n$ with the first column removed. As the first column of $A_n$ is constantly $1$, the vectors $v_k-v_m$ for $1\le k\le m-1$ are left eigenvectors of $A_n$. And clearly they are linearly independent.

Thus for $n$ an odd prime, we get $\operatorname{rank}(A_n)\le\lfloor(n+3)/2\rfloor$.

A modest start, but before doing so, one suggestion: I would index the columns and rows from $0$ to $n-1$, so $a_{ij} = (-1)^{\lfloor 2ij/n\rfloor}$.

Let $n=2m+1$ be an odd prime. Then $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity for $1\le j, k\le n-1$.

Let $v_k$ be the row vector with $1$ in positions $k$ and $n-k$ and $0$ elsewhere. Thus $v_k$ is a left eigenvector for $1\le k\le n-1$ of $A_n'$ where $A_n'$ is the matrix $A_n$ with the first column removed. As the first column of $A_n$ is constantly $1$, the vectors $v_k-v_m$ for $1\le k\le m-1$ are left eigenvectors of $A_n$. And clearly they are linearly independent.

Thus for $n$ an odd prime, we get $\operatorname{rank}(A_n)\le\lfloor(n+3)/2\rfloor$.

The argument generalizes to give the upper bound of the rank for arbitrary $n$. For simplicity I assume that $n$ is odd. The even case is slightly more involved. Let $v_k$ be as above, and let $a_j$ be the $j$'th column of $A_n$. Since $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity if and only if $n$ does not divide $2kj$, we get $v_ka_j=0$ if $n\nmid 2kj$, and $v_ka_j=2$ otherwise.

Set $d=\operatorname{gcd}(n, k)$. If $k$ does not divide $n$, then $d<k$. Furthermore, $n$ divides $2kj$ if and only if $n$ divides $2(k-d)j$. Thus $v_k-v_{k-d}$ is an eigenvector of $A_n$ for each $k$ which does not divide $n$. If we restrict to $1\le k\le m=(n-1)/2$ again, and note that each proper divisor of $n$ is in this range, we see that we got the right number of linearly independent vectors.