how analytically (or with matlab) can i find the solution to the following algebraic problem? Here is the problem: find $x_k$'s ($x_k\in R$) such that
$\max_{i} \{|c_i+\sum_k x_k d_{ki}| \}=\gamma$,
where $c_i$ and $d_{ki}$ are constant numbers in $R$. 
I'm looking for the set of $x_k$ that satisfies the above condition.
For example 
$\max\{|2-3x_1+x_2|,|1+2x_1+x_2|\}=1$,

Edited: to make the example more clear. 
Consider this one
$\max\{|2-3x_1+x_2|,|1+2x_1+x_2|, |1-x_1-x_2|\}=1$,
That is, the number of equations is not equal to the number of variables. 
 A: If we are given $m$ linear functions
$$\phi_i:\quad{\mathbb R}^n\to{\mathbb R}, \qquad x\mapsto \phi_i(x):=\langle d_i,x\rangle +c_i\qquad(1\leq i\leq m)$$
and a real $\gamma>0$ the $2m$ inequalities
$$-\gamma\leq \phi_i(x)\leq \gamma\qquad(1\leq i\leq m)$$
define a convex polytope $P\subset{\mathbb R}^n$ (which may be empty, and need not be bounded). The set you are interested in is the boundary $\partial P$ of this polytope. This boundary can have a complicated combinatorial structure. The possible numbers of vertices, edges, $\ldots$, facets form an intensive area of research. This is to say that your problem is computationally hard as soon as $m$ and $n$ get larger.
A simple case is treated in the following first version of this answer:
Assume that the matrix $D=[d_{ki}]$  is square and nonsingular, and consider the affine map
$$A:\quad x\mapsto y:=D'x+c\ .$$
(Your indexing of the $d_{ki}$ is somewhat unfortunate, therefore the $'\>$) You are interested in the set $$S:=\{x\in{\mathbb R}^n\>|\>\max_i|y_i|=\gamma\}\ .$$
Now the set $\{y\in {\mathbb R}^n\>|\>\max_i|y_i|=\gamma\}$ is the surface $\partial C$ of the $n$-dimensional cube $$C:=\{y\in {\mathbb R}^n\>|\>-\gamma\leq y_i\leq\gamma \  (1\leq i\leq n)\}\ ,$$
and is the union of $2n$ such cubes of one dimension less (an ordinary $3$-dimensional cube has $6$ two-dimensional square faces).
It follows that
$$S=A^{-1}(\partial C)=(D')^{-1}(\partial C -c)\ .$$
A: EDIT: The answer below gives one and all solutions for the problem of finding a $x_k\in\mathbb{R}$ such that
$\max_i\{\lvert c_i+\sum_k x_k d_{ki}\rvert\}=\gamma$
where $c_i$ and $d_{ki}$ are constant numbers in $\mathbb{R}$.
The solution for the problem of finding all the possibles $x_k$ that satisfies the equation above is given after the approach that finds one solution.
For one solution:
I've found the following solution method, verify if it fits your requirements.
I focused on the solution of the example but it might work for any problem.
Note that any solution for you problem lies on the border of the following region
\begin{gather}
-1 \leq 2 - 3x_1 + x_2 \leq 1\\
-1 \leq 1 +2x_1 +2x_2 \leq 1
\end{gather}
Therefore solving the optimization problem 
\begin{align}
\max\quad &c^Tx\\
\textrm{s.t.:}\quad&-1 \leq 2 - 3x_1 + x_2 \leq 1\\
&-1 \leq 1 +2x_1 +2x_2 \leq 1
\end{align}
where $c$ is a nonzero vector, will result in a solution that satisfies your conditions.
The feasible region is shown in the following plot

For all solutions:
For all solutions you can do a similar approach, create a polyhedron given by the convex relaxation of the problem. The equations are given by 
\begin{align}
-\gamma \leq c_i+\sum_k x_k d_{ki}\leq \gamma
\end{align}
for all $i$.
Then use a vertex enumeration algorithm to obtain all the vertex of the polyhedron. Suggested links


*

*2 - related question in the mathoverflow,

*3 - Avis-Fukuda Algorithm for Vertex Enumeration Problems (A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra),

*4 - Old paper about the subject might be interesting option.


You can find more over internet over the keyword "Vertex enumeration problem".
