Number of solutions of system of linear equations over finite field Suppose $F=GF(2^8)$. Let $u_1,u_2\in K=GF(2^4)$ be linearly independent elements. The functions $x\mapsto tr_n (u_ix)$ are linear functions from $F\to GF(2)$, $i=1,2$. Here $tr_n$ denotes the absolute trace.
Since the functions are linear, I know that there are exactly $2^7$ elements $x$ such that $tr_n(u_ix)=0$, for $i=1,2$.
Computationally, I observed that there are exactly $2^6$ elements such that $ tr_n (u_1x)=0$ and $ tr_n (u_2x)=0$. Since $u_i\in K$, I know that for $x\in K$, both of the traces will be equal to $0$. But how do I determine the remaining $2^6-2^4$ elements. How do I prove that the number of solutions is exactly $2^6$. I have a feeling that it has to do with the linear independence of $u_1$ and $u_2$, but I do not know how to use it.
 A: Proving that there are exactly $2^6$ solutions is easy.
Let
$$V_i=\{x\in F\mid tr(u_ix)=0\},$$
$i=1,2$, be the sets of solutions to one of the equations. As you observed they are kernels of a linear transformation $f_i:F\to GF(2), x\mapsto tr(u_ix)$. Because $u_1\neq0\neq u_2$, both are surjective, and, by rank-nullity, have dimension $7$.
Linear independence is equivalent to the assumption that $u_1$ are $u_2$ are distinct and non-zero. The key is the following
Claim. The subspaces $V_1$ and $V_2$ are not equal.
Proof. Assume contrariwise that $V_1=V_2$. Let $y_1,y_2,\ldots,y_7$ be a basis of $V_1$. We can extend it to a basis of $F$ by joining an eighth element $y_8$. As $y_2\notin V_1=V_2$ we have $tr(u_1y_8)=1=tr(u_2y_8)$. Together with the facts $tr(u_iy_j)=0$, $i=1,2, j=1,2,\ldots,7$. This implies that
$$
tr((u_1+u_2)y_j)=0
$$
for all $j=1,2,\ldots,9$. In other words, $x\mapsto tr((u_1+u_2)x)$ vanishes on all of $F$. By basic properties of the trace maps this implies that $u_1+u_2=0$. In other words $u_1=u_2$. A contradiction.
It follows that $V_1\cap V_2$ is a 6-dimensional subspace. We can re-interpret the intersection as the kernel of the restriction of the transformation $f_2$ to $V_1$:
$$
V_1\cap V_2=\operatorname{Ker}(f_2\vert_{V_1})=\{x\in V_1\mid f_2(x)=0\}.
$$
The image of $f_2\vert_{V_1}$ is a subspace of $GF(2)$, so has dimension either $0$ or $1$. Two cases:

*

*If $f_2\vert_{V_1}$ is the zero map, then it follows that $V_1=V_2$ &endash; a case we excluded.

*If $f_2\vert_{V_1}$ is surjective then, by rank-nullity, its kernel is 6-dimensional. Implying that $V_1\cap V_2$ has exactly $2^6$ elements.


For generalizations they key is that the (symmetric) bilinear form $B:F\times F\to GF(2)$
$$
B(x,y)=tr(xy)
$$
is non-degenerate. In other words, given a $y\in F$ such that $B(x,y)=0$ for all $x\in F$, we can conclude that we must have $y=0$. For the trace form this is clear.
Whenever we have a non-degenerate bilinear form $B:V\times V\to GF(2)$, $\dim V=n$, it follows that to each subspace $W\subseteq V$, its orthogonal subspace
$$W^\perp=\{z\in V\mid B(x,z)=0 \ \text{for all $x\in W$}\}$$
has the complementary dimension:
$$
\dim W+\dim W^{\perp}=\dim V.
$$
So if next time you have three linearly independent elements $u_1,u_2,u_3$, it is automatic that the system $tr(u_ix)=0$, $i=1,2,3$, has exactly $2^{8-3}=2^5$ solutions.
Undoubtedly you noticed how I used non-degeneracy of the trace form to conclude that $u_1+u_2=0$.
