Any element in a boolean extension field $a\in GF(2^n)$ can be presented by a boolean vector $a\_{(2)} \in GF(2)^n$. For any element $a\in GF(2^n)$, there exists a boolean matrix $M\_a\in GF(2)^{n\times n}$ such that $(ab)\_{(2)} = M\_a \cdot (b)\_{(2)}$.


**The question:**
For any non-zero $\vec v\in GF(2)^n$,
is the mapping $a\mapsto \vec v^T M\_a$ a bijection?
In other words, if $a\in GF(2^n)$ is a uniform random field element, is $\vec v^T M\_a$ uniform random as well?


Note that, the mapping $a \mapsto M\_a \vec v$ is a bijection for any non-zero $\vec v\in GF(2)^n$.
Because there exists non-zero $v\in GF(2^n)$ that $v\_{(2)} = \vec v$,
then $M\_a \vec v = M\_a \cdot v\_{(2)} = (av)\_{(2)}$.
In other words, if $a$ if random,
so every column vector in $M\_a$ is random, every linear combination of column vectors in $M\_a$ is random. I wonder if the same holds for its row vectors.



Does binary extension field multiplication matrix have random rows?
The function $a \mapsto M\_a$ is a linear transformation from $GF(2)^n$ to $GF(2)^{n \times n}$, so $a \mapsto \vec{v}^{T} M\_a$ is a linear transformation from $GF(2)^n$ to the dual vector space $(GF(2)^n)^\*$. Both of these vector spaces are $n$-dimensional. To see that the linear transformation $a \mapsto \vec{v}^{T} M\_a$ is a bijection, we will show that its kernel is zero-dimensional, i.e. the only $a \in GF(2)^n$ such that $\vec{v}^{T} M\_a=0$ is $a=0$.


By assumption $\vec{v} \neq 0$, so there exists $\vec{w} \in GF(2)^n$ such that $\vec{v}^{T} \vec{w} \neq 0$. Let $b \in GF(2^n)$ be the field element such that $b\_{(2)} = \vec{w}$. If $a \neq 0$, we may define $c = a^{-1} b \in GF(2^n)$ and $\vec{x} = c\_{(2)} \in GF(2)^n$. Then we have $M\_a \vec{x} = (a c)\_{(2)} = (a a^{-1} b)\_{(2)} = b\_{(2)} = \vec{w}$ so $\vec{v}^{T} M\_a \vec{x} = \vec{v}^{T} \vec{w} \neq 0$. Hence, when $a \neq 0$ it follows that $\vec{v}^{T} M\_a \neq 0$, so there are no non-zero vectors in the kernel of the linear transformation $a \mapsto \vec{v}^{T} M\_a$, as claimed.


