Characterize the nullspace of a given matrix in $\mathbb{F}_2^{n\times n}$ Let $J_n$ denote the following square matrix of side $n$:
$$
\begin{bmatrix}
  1 & \dots & 1 \\
  \vdots & \ddots & \vdots \\
  1 & \dots & 1
\end{bmatrix}
$$
and let $I_n$ denote as usual the square identity matrix of side $n$.
Let $A_n$ denote the following square matrix of side $n^2$:
$$
\begin{bmatrix}
  J_n & I_n & \dots & I_n \\
  I_n & J_n & \ddots & \vdots \\
  \vdots & \ddots & \ddots & I_n \\
  I_n & \dots & I_n & J_n
\end{bmatrix}
$$
that is, the block square matrix of side $n$ whose blocks on the main diagonal are $J_n$, and any other block is $I_n$.
Can we characterize its nullspace when viewed as a matrix in $\mathbb{F}_2^{n\times n}$? I'm mostly interested in a basis of its nullspace, but finding its cardinality is also ok.
MOTIVATION: This matrix arises when solving this problem using the approach described by the handout linked in EDIT 2. It's interesting to note that the underlying problem gives a proof that $A_n$ is invertible for even $n$, therefore the interesting case is $n$ odd (see the argument by @Aryabhata here).
 A: First thing,
in case $n=2k+1$ you can find that $A_n(\sum_i e_i)=\sum_i e_i$. Many vectors are in the kernel, to show them let's call $$\forall s \equiv 1 \  (n) \  \ v_s:= \sum^{s+n-1}_{i=s}e_i.$$ Actually $\forall s,k : s\not=k$ and $s,k \equiv 1 \ (n) $ we get that $A_n(v_s+v_k)=0$ (these are $n\choose{2}$) and $n-1$ are linearly independent, they are $$ \{w_s: w_s=v_s+v_{s+1}\}.$$ But we are not done.  You also get $$A_n(\sum_{i \not\equiv j (n)}e_i)=0$$ So $$ \{^jv :\  ^jv = \sum_{i \not\equiv j (n)}e_i \}$$ are in the kernel. They are $n$ but just $n-1$ of them are linearly independent as before.
A: Just an update to Ivan's answer. We have
$$\dim\ker A_n \leq 2n-2$$
since:
$$ A_n = (I_n\otimes U_n+U_n\otimes I_n - I_n\otimes I_n) = (U_n\oplus U_n - I_{n^2}),$$
where $I$ is the identity matrix and $U$ is the matrix whose elements are just ones.
Using the theory of the Kronecker sum/product of matrices, we have:
$$\operatorname{spec}{A_n} =  \operatorname{spec}(U_n)+\operatorname{spec}(U_n)-1,$$
so the spectrum of $A_n$ over $\mathbb{R}$ is made by $2n-1$ (once), $-1$ ($(n-1)^2$ times) and $n-1$ ($2n-2$ times). This gives that if $n\equiv 0\pmod{2}$ then $A_n$ is invertible, and if $n\equiv 1\pmod{2}$ there are at most $2n-2$ vectors in $\ker A_n$. Since Ivan just proved the inequality in the other direction, we have:
$$\dim\ker A_n = 2n-2.$$
