  We propose a new deterministic Kaczmarz algorithm for solving consistent
linear systems $A\mathbf{x}=\mathbf{b}$. Basically, the algorithm replaces
orthogonal projections with reflections in the original scheme of Stefan
Kaczmarz. Building on this, we give a geometric description of solutions of
linear systems. Suppose $A$ is $m\times n$, we show that the algorithm
generates a series of points distributed with patterns on an $(n-1)$-sphere
centered on a solution. These points lie evenly on $2m$ lower-dimensional
spheres $\{\S_{k0},\S_{k1}\}_{k=1}^m$, with the property that for any $k$, the
midpoint of the centers of $\S_{k0},\S_{k1}$ is exactly a solution of
$A\mathbf{x}=\mathbf{b}$. With this discovery, we prove that taking the average
of $O(\eta(A)\log(1/\varepsilon))$ points on any $\S_{k0}\cup\S_{k1}$
effectively approximates a solution up to relative error $\varepsilon$, where
$\eta(A)$ characterizes the eigengap of the orthogonal matrix produced by the
product of $m$ reflections generated by the rows of $A$. We also analyze the
connection between $\eta(A)$ and $\kappa(A)$, the condition number of $A$. In
the worst case $\eta(A)=O(\kappa^2(A)\log m)$, while for random matrices
$\eta(A)=O(\kappa(A))$ on average. Finally, we prove that the algorithm indeed
solves the linear system $A^T W^{-1}A \mathbf{x} = A^T W^{-1} \mathbf{b}$,
where $W$ is the lower-triangular matrix such that $W+W^T = 2AA^T$. The
connection between this linear system and the original one is studied. The
numerical tests indicate that this new Kaczmarz algorithm has comparable
performance to randomized (block) Kaczmarz algorithms.
