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.