In Kyber the matrix $A$ has special structure. Specifically, in Kyber512 it is of the form
$$\begin{pmatrix}N_{1,1}&N_{1,2}\\ N_{2,1}&N_{2,2}\end{pmatrix}$$
in Kyber768 it is of the form
$$\begin{pmatrix}N_{1,1}&N_{1,2}&N_{1,3}\\ N_{2,1}&N_{2,2}&N_{2,3}\\ N_{3,1}&N_{3,2}&N_{3,3}\end{pmatrix}$$
and in Kyber1024 it is of the form
$$\begin{pmatrix}N_{1,1}&N_{1,2}&N_{1,3}&N_{1,4}\\
N_{2,1}&N_{2,2}&N_{2,3}&N_{2,4}\\ N_{3,1}&N_{3,2}&N_{3,3}&N_{3,4}\\ N_{4,1}&N_{4,2}&N_{4,3}&N_{4,4}\end{pmatrix}$$
where each $N_{i,j}$ is a negacirculant matrix of the form
$$\begin{pmatrix} c_0 & c_1 & c_2&\ldots & c_{511}\\
-c_{511} & c_0 & c_1 &\ldots & c_{510}\\
-c_{510} & -c_{511} & c_0 &\ldots & c_{509}\\
\vdots & & &\ddots &\vdots\\
-c_1 &-c_2&-c_3&\ldots& c_0\end{pmatrix}.$$
The special form of this matrix means that the matrix multiplication
$$\begin{pmatrix} c_0 & c_1 & c_2&\ldots & c_{255}\\
-c_{255} & c_0 & c_1 &\ldots & c_{254}\\
-c_{254} & -c_{255} & c_0 &\ldots & c_{253}\\
\vdots & & &\ddots &\vdots\\
-c_1 &-c_2&-c_3&\ldots& c_0\end{pmatrix}\begin{pmatrix} \ell_{255}\\ \ell_{254}\\ \vdots\\ \ell_0\end{pmatrix}=\begin{pmatrix} r_{255}\\ r_{254}\\ \vdots\\ r_0\end{pmatrix}.$$
Is consistent with the multiplication $(c_0+c_1X+\cdots c_{255}X^{255})(\ell_0+\ell_1X+\cdots+\ell_{255}X^{255})=r_0+r_1X+\cdots+r_{255}X^{255}$ when the multiplication is performed modulo $X^{256}+1$.
This means that in Kyber512, the expression $A\mathbf s+\mathbf e$ can equally be thought to represent the following matrix equation over the ring $\mathbb Z[X]/\langle q, X^{256}+1\rangle$
$$\begin{pmatrix} n_{1,1}(X) & n_{1,2}(X)\\ n_{2,1}(X) & n_{2,2}(X)\end{pmatrix}\begin{pmatrix}s_1(X)\\ s_2(X)\end{pmatrix}+\begin{pmatrix}e_1(X)\\ e_2(X)\end{pmatrix}$$
(with similar expressions for Kyber768 and Kyber1024). This is a module learning with errors problem with 2 samples (respectively 3 and 4 in the cases of Kyber768 and Kyber1024). We believe that the components of the answer vector are statistically indistinguishable from uniform elements of our ring.
To "brute force" a solution one would try all possible values of $s_1(X)$ and $s_2(X)$ to see if when multiplied by $A$ they producer an answer close to the public key. In Kyber512 the coefficients of the $s_i(X)$ are all from the range $-3,-2,-1,0,1,2,3$ which gives $7^{512}$ possibilities for the private key. Breaking Kyber512 is "only" meant to be as hard as brute-forcing a 128-bit key for which there are $2^{128}$ possibilities. Even if we are intelligent about our exhaust, the key space is much larger than that permitted by the security requirements.
