Consider a system of linear equations over the binary field (either homogeneous or inhomogeneous), which we can denote in matrix form as $Ax = b$ for some $b\in \mathbb{F}_2^n$ and $A\in\mathbb{F}_2^{n\times n}$. I'm interested in the case where $A$ is circulant, i.e. where a column is the translation of the previous column (modulo the total number of columns):
$A = \begin{pmatrix} a_0 & a_{n-1} & \cdots & a_1 \\ a_1 & a_0 & \cdots & a_2\\ \vdots & \vdots & \ddots & \vdots\\ a_{n-1} & a_{n-2} & \cdots & a_0 \end{pmatrix} $
Hence $A$ is described by a column vector $a\in\mathbb{F}_2^n$ and the system can be written (see Wikipedia) as the convolution of $a$ and $x$ (with indices modulo $n$):
$$ a * x = b \iff (a*x)_i = \sum_j a_{i+j}x_j = b_i$$
This can be solved by performing a discrete Fourier Transform, where convolution is multiplicative (element wise), and then transforming back:
$$ FT(a*x) = FT(b) \Rightarrow FT(a)\odot FT(x) = FT(b) \Rightarrow FT(x) = FT(b) ./FT(a) $$
and finally $x = FT^{-1}( FT(b) ./FT(a) )$. The problem stands with the fact that the Fourier transform is inherently defined over the complex field (or real, for hermitian A), whereas I'm considering $A$ over the binary field.
How can this be generalized over the binary field? If it cannot, can you provide a reason for why we should not expect a generalization to be possible (e.g. a counterexample)? I have not managed to find much online, beyond this: https://arxiv.org/pdf/1801.00399
I would also be interested in the more general case with $A\in\mathbb{F}_2^{m\times n}, x\in\mathbb{F}_2^n, b\in\mathbb{F}_2^m$ and we have a row-circulant matrix, though I imagine that would be more complicated in general.
