It would be good to have a reference for this "weak Nullstellensatz", since it contains the core of the argument, and also is not a standard name

@ThomasSauvaget Good point - for instance $A_n$ has trace zero iff $n \equiv 2 \pmod 4$. I also computed some characteristic polynomials, but did not see any patterns at first glance

@MaartenHavinga I don't think that $n = 8$ gives a Hadamard matrix. Indeed $A_8 A_8^T$ is not even diagonal

Thanks for the data! Any guesses as to the product of the nonzero invariant factors?

I tried playing with prime $n$, and it seems like your suggestion of $e_k - e_{n-k}$, $1 \le k < n/2$ being in the row (= column) space checks out - although the coefficients I found for the linear combinations (wrt rows of $A_n$) are not easy to predict, they do seem to be only supported in the latter half of rows (with a single exception for $k = 1$). Also I believe the additional 2 vectors needed in this case can be chosen to be $e_0$ and $\sum_{k=1}^{\lfloor n/2 \rfloor} e_k$ (both of which only involve 2 rows of $A_n$)

In fact I did use 0-based indexing in my own calculations (now edited). This is a nice construction of the correct number of linearly independent vectors in $\ker(A_n)$, so it remains to show that they span the kernel - any ideas?

@darijgrinberg Maybe you were secretly thinking about $\dim \ker$ instead of rank :) Somewhat related, I don't know if there's a good way of viewing $A_n, A_m$ as blocks inside $A_{nm}$