The matrix with entries $\pm 1$ is surjective? Consider matrix $A$ of size $n\times 2^n$ such that each column is a vector in $\{-1, +1\}^n$. It is clear that there are exactly $2^n$ distinct columns.
I have the impression that the linear map corresponding to $A$ is surjective? Indeed, it is clear in 2D, 3D. It is correct in higher dimension?
To prove the surjection, I know that we can use: definition of surjective function, rank–nullity theorem, or computing rank. But I could not find any solution.
 A: Two quick solutions:
Solution 1: Let $e_1,\dots,e_n$ denote the standard basis of $\Bbb R^n$ (i.e. the columns of the identity matrix). Let $v$ denote the column vector $v = (1,1,\dots,1)$. Each vector $e_i$ can be expressed as a linear combination of the columns of $A$ in the following way:
$$
e_i = \frac 12 v - \frac 12 (v - 2e_i).
$$
Thus, each vector $e_i$ lies in the column space of $A$. Since the vectors $e_1,\dots,e_n$ form a basis, we can conclude that the associated linear map is surjective.*
Solution 2: The case of $n=2$ can be handled separately**. For $n \geq 2$, note that $A$ contains as a submatrix
$$
M = \pmatrix{-1&1&\cdots & 1\\
1&-1 & \cdots & 1\\
\vdots & \vdots & \ddots & \vdots\\
1 & 1 & \cdots & -1}.
$$
With the techniques outlined here, it's easy to see that the determinant of $M$ will be
$$
\det(M) = (-2)^{n-1}\cdot(n-2) \neq 0.
$$
Thus, $M$ in invertible, which means it has linearly independent columns. So, the columns of $A$ (which contain the columns of $M$) span $\Bbb R^n$.
* (Note 1): Concretely, the $n=2$ case can be handled by considering the invertible submatrix $M = \pmatrix{1&1\\1&-1}$.
** (Note 2): Solution 1 can be reframed as finding a $2^n \times n$
matrix $B$ such that $AB = I_{n \times n}$, i.e. a "right-inverse" to $A$.
