\documentclass[12pt]{amsart} \usepackage{psfig} \oddsidemargin 18pt \evensidemargin 18pt \marginparwidth 40pt \marginparsep 10pt \topmargin 0pt %\headsep .5in \textheight 624pt \textwidth 432pt \headheight 7pt \let\cal\mathcal \title{Bases in Systems of Simplices and Chambers} \author{Tatiana Alekseyevskaya} \thanks{Supported by the Gabriella and Paul Rosenbaum Foundation; part of these results was obtained at MSRI supported by NSF grant DMS 9022140.} \address{Department of Mathematics\\ Rutgers University\\ Piscataway, NJ 08855\\ USA} \email{tva@math.rutgers.edu} \date{\today} \newtheorem{definition}{Definition}[section] \newtheorem{theorem}[definition]{Theorem} \newtheorem{open}{Problem} \newtheorem{lemma}[definition]{Lemma} \newtheorem{corollary}[definition]{Corollary} \newtheorem{proposition}[definition]{Proposition} \begin{document} %\tableofcontents \begin{abstract} We consider a finite set $E$ of points in the $n$-dimensional affine space and two sets of objects that are generated by the set $E$: the system $\Sigma$ of $n$-dimensional simplices with vertices in $E$ and the system $\Gamma$ of chambers. The incidence matrix $A= \parallel a_{\sigma, \gamma}\parallel$, $\sigma \in \Sigma, \ \gamma \in \Gamma$, induces the notion of linear independence among simplices (and among chambers). We present an algorithm of construction of bases of simplices (and bases of chambers). For the case $n=2$ such an algorithm was described in \cite{A}. However, the case of $n$-dimensional space required a different technique. It is also proved that the constructed bases of simplices are geometrical (according to \cite{A}). \end{abstract} \maketitle \section{Introduction.} Let $E=(e_1,e_2, \ldots , e_N), \ N>n, $ be a finite set of points in an $n$-dimensional affine space $V$. Let $P= conv(E)$ be the convex hull of $E$. Let $\sigma=\sigma(e_{i_1}, \ldots , e_{i_{n+1}}) $ be the $n$-dimensional simplex with the vertices $e_{i_1}, \ldots , e_{i_{n+1}} \in E$. Denote by $\Sigma$ the set of all such simplices $\sigma$. All the simplices $\sigma$ (as a rule overlapping) cover the polytope $P$. The simplices $\sigma $ divide the polytope $P$ into a finite number of chambers $\gamma$ (see Definition (\ref{def})). Denote by $\Gamma$ the set of all chambers $\gamma$ in $P$. \begin{definition} \label{def} Let $\sigma \in \Sigma$ and $\tilde{\sigma}$ be the boundary of $\sigma$. Let $\tilde{\Sigma}= \bigcup_{\sigma \in \Sigma} \tilde{\sigma}$ and $\bar{P}= P \setminus \tilde{\Sigma}$. Let $\bar{\gamma}$ be a connected component of $\bar{P}$ and $\gamma$ be closure of $\bar{\gamma}$. We call $\gamma$ a chamber and $\bar{\gamma}$ an open chamber. \end{definition} Let $A$ be the incidence matrix between simplices and chambers, i.e. $$\parallel a_{\sigma,\gamma}\parallel =1 \hbox{ iff } \gamma \subset \sigma.$$ Consider the linear space $V_\Sigma$ generated by the rows of $A$ and the linear space $V_\Gamma$ generated by the columns of $A$ over some field of characteristic 0. Due to one-to-one correspondence between the rows of $A$ and the simplices $\sigma \in \Sigma$, we can speak about a linear combination of simplices instead of a linear combination of the corresponding rows of $A$. An important question is to construct bases of simplices and bases of chambers, i.e. bases in $V_\Sigma$ (or in $V_\Gamma$) that consists of simplices (or chambers) and not of their linear combinations. \smallskip A basis of simplices can be also defined as follows. Let $\phi_{\sigma} (x)$ be the characteristic function of a simplex $\sigma$, i.e. $$\phi_ \sigma (x) =1,\ \if\ \ x \in \sigma\ \ and\ \ \phi_\sigma (x) =0,\ \ x \not \in \sigma.$$ A basis of simplices is a maximal subset of simplices such that their characteristic functions $\phi _\sigma (x)$ are linearly independent. \smallskip In this paper we will describe (Section 2) the inductive algorithm of constructing bases of simplices and bases of chambers in the $n$-dimensional affine space; the algorithm uses the case $n=2$ (see \cite{A}) as the first step of induction. In Sections 3, 4 we prove that the set $B$ of simplices and the set $B'$ of chambers constructed by the algorithm are indeed bases in $V_\Sigma$ and in $V_\Gamma$ respectively. \section{Construction of a basis of simplices and a basis of chambers.} \subsection{A special ordering of points $e \in E$ and related polytopes.} Let $E =\{e_1, \ldots , e_N\}$ be a set of points in an $n$-dimensional affine space $V^n$, $\Sigma$ the set of $n$-dimensional simplices $\sigma$ with the vertices in $E$ and $\Gamma$ the set of chambers $\gamma$ (defined in Introduction.) We will define an ordering of points $e_i \in E$ which is essential in the construction. \begin{lemma} \label{lemma} Let $E=\{e_1,e_2, \ldots, e_N \}$ be a finite set of points in the $n$-dimensional affine space. There exists an ordering $e_{i_1}, e_{i_2},\ldots, e_{i_N}, \ \ e_{i_k}\in E, $ such that $for \ k=1, \ldots, N$ \begin{equation} \label{conv} conv(e_{i_1}, \ldots , e_{i_k}) \cap conv(e_{i_{k+1}}, \ldots , e_{i_N}) =\emptyset, \end{equation} and there exists a hyperplane $H_k$ which separates the polytopes \begin{equation} \label{setF} F_k =conv (e_{i_1}, \ldots , e_{i_k}) \end{equation} and \begin{equation} \label{setE} P_k =conv(e_{i_{k+1}},\ldots , e_{i_N})= conv (E \setminus (e_{i_1}, \ldots , e_{i_k})). \end{equation} We assume also $F_0 =\emptyset , P_N = \emptyset, P_0 =conv (E)=P, F_N =conv (E)=P$. \end{lemma} This lemma is proved, for example, in \cite{A}. The ordering $e_1, \ldots, e_N$ satisfying Lemma \ref{lemma} yields a shelling of the polytope $P$, see \cite{DK}. \smallskip Let the ordering $e_1, \ldots, e_N$ satisfy (\ref{conv}). Consider the sequence of polytopes $P_0=P, P_1, \ldots, P_N=\emptyset $ defined by formula (\ref{setE}). We have $P_0 \supset P_1 \supset \ldots \supset P_N$. Let us denote \begin{equation} \label{SK} S_k=\overline{P_{k-1} \setminus P_k}, \end{equation} where $\overline{A}$ means the closure of the set $A$. Let $int(S)$ be the interior of $S$. It is easy to check that the following statements are true: \begin{enumerate} \item{ Each ordering $e_1, \ldots , e_N$ determines a decomposition of the polytope $P$: \begin{equation} \label{decomp} P =\bigcup_{i=1}^{N-n}S_i, \end{equation} where $int(S_i)\cap int(S_j) = \emptyset$ for $i \neq j$.} \item{$int(S_k) \cap E = \emptyset$ for $k=1, \ldots, N-n$. } \item{The polytope $S_k$ is part of the convex cone with the vertex $e_k$ and bounded by some part $\cal{L}_k$ of the boundary of $P_{k-1}$, (where $\cal{L}_k= S_k \cap P_{k-1}$). Note that the polytope $S_k$ is not necessarily convex\footnote{The polytopes $S_k$ are considered in more detail in \cite{A}.}.} \item{\begin{equation} \label{SP} P= S_1 \cup \ldots \cup S_{k-1} \cup P_{k-1} \end{equation}} \end{enumerate} \subsection{ A map from the polytope $P$ to the hyperplane $H_k$.} Let an ordering of points $e_1, \ldots , e_N$ satisfy (\ref{conv}). Consider the point $e_k \in P_{k-1}$ and the corresponding hyperplane $H_k$. For a segment $(e_k, e_i), \ i=k+1, \ldots, N$ let us denote \begin{equation} \label{EIK} e^k_i=(e_k, e_i) \cap H_k. \end{equation} Thus, on the hyperplane $H_k$ we obtained the set $E_k$ of points $e^k_1, e^k_2, \ldots , e^k _{N_k}$. (Note that $N_k \leq N-k$ since the points $e \in E$ are not necessarily in general position.) In the hyperplane $H_k$ we use the points $e^k \in E_k$ to construct simplices $\sigma^k$ and chambers $\gamma^k$ in the same way as it was done for the set $E$ in $V^n$ . Let $\Sigma_k$ be the set of all these simplices $\sigma^k$ and $\Gamma _k$ the set of all chambers $\gamma^k$. Let $\sigma^k=\sigma(e^k_{i_1}, \ldots , e^k_{i_n}) \in \Sigma_k$. We denote by $\overrightarrow{(e_k, e^k_{i_j})}$ the ray starting at $e_k$ and passing through the point $(e^k_{i_j})$. Consider the following map: \begin{equation} \label{mu} \mu :\sigma^k \mapsto \sigma,\ \ where \ \sigma= \sigma(e_k, e_{i_1}, \ldots ,e_{i_n}), \end{equation} and where $e_{i_j}\in E$ is the nearest point to the point $e_k$ on the ray $\overrightarrow{(e_k, e^k_{i_j})}$. It is clear that $\sigma= \mu(\sigma^k) \in \Sigma$. The map $\mu$ is an injection and has the following easy to check property. \begin{proposition} \label{prop1} Let $\sigma^k, \sigma^k_0 \in \Sigma_k$ be open simplices such that $\sigma^k \cap \sigma^k_0 = \emptyset$. Then $\mu (\sigma^k ) \cap \mu (\sigma^k_0) =\emptyset$. \end{proposition} Consider the set of points $E_k$ in the hyperplane $H_k$. Let us reorder $e^k \in E_k$ according to (\ref{conv}). Let $e^k_1, e^k_2, \ldots , e^k _{N_k}$ be such an ordering. Similarly to formulas (\ref{setE}) and (\ref{SK}) we denote \begin{equation} \label{PS} P^k=P^k_0= conv(E_k),\ P^k_j= conv(e^k_{j+1}, \ldots , e^k_{N_k}), \ \ S^k_j= P^k_{j-1} \setminus P^k_j \end{equation} where $j= 1, \ldots, N_k$. For these $(n-1)$-dimensional polytopes the formulas analogous to (\ref{decomp}) and (\ref{SP}) hold: \begin{equation} \label{PK} P^k =\bigcup_j S^k_j, \end{equation} where $int(S^k_i) \cap int( S^k_j)= \emptyset$ for $i \neq j,$ and \begin{equation} \label{PK1} P^k= S^k_1 \cup \ldots \cup S^k_{j-1} \cup P^k_{j-1}. \end{equation} On the polytopes $S^k_j$ and $P^k_j$ let us define the following map $\tau$: $\tau(S^k_j)$ is an $n$-dimensional cone with the vertex $e_k$ and generated by the rays $\overrightarrow{(e_k, x)}$, where $x \in S^k_j$. The map $\tau(P^k)$ is defined similarly. Clearly, the following decomposition holds: \begin{equation} \label{tau} \tau(P^k) = \bigcup _i \tau(S^k_i), \end{equation} where $int(\tau(S^k_i)) \cap int( \tau(S^k_j))= \emptyset$ for $i \neq j$. \subsection{ Algorithm of construction of the set $B$ of simplices and the set $B'$ of chambers.} We will construct the set $B \subset \Sigma$ of simplices and the set $B'$ of chambers and will prove in Sections 3 and 4 that the set $B$ is a basis in $V_\Sigma$ and the set $B'$ is a basis in $V_\Gamma$. The algorithm of construction of $B$ and $B'$ is inductive on the dimension $n$ of the affine space $V^n$. Let an ordering of points $e_1, \ldots , e_N$ satisfy (\ref{conv}). For each point $e_k$ we construct a set $B_k$ of simplices $\sigma \in \Sigma$ and a set $B'_k $ of chambers $\gamma \in \Gamma$. Then we define $B= \bigcup B_k$ and $B' = \bigcup B'_k$. \smallskip {\bf First step ($n=2$).} The points $e_1, \ldots , e_N$ lie on the affine plane $V^2$. Let us denote by $q$ an edge of a simplex $\sigma \in \Sigma$ and by $Q$ the set of all edges of all simplices $\sigma \in \Sigma$. Consider the point $e_k \in P_{k-1}$. In $P_{k-1}$ from the point $e_k$ there are following edges $q_i =(e_k, e_i)$, where $i \in (k+1, \ldots , N)$. Note that since the points $e \in E$ are not necessarily in general position, some of these edges may coincide and several points $e_i, \ i\in (k+1, \ldots , N)$ may lie on the same edge. Let $q_i=(e_k, e_i)$ and $q_j =(e_k, e_j)$, where $i,j \in (k+1, \ldots, N)$, be two neighbor edges with the vertex $e_k$ (i.e. there is no other edge $q=(e_k,e_m),\ m \in(k+1, \ldots , N)$ which lies between $q_i$ and $q_j$). Let the point $e_i$ be the nearest point of $E$ to the point $e_k$ on the edge $q_i$ and, respectively, $e_j$ the nearest point to the point $e_k$ on the edge $q_j$. Let $\sigma= \sigma (e_k, e_i, e_j)$. We define $B_k$ as the set of all such simplices $\sigma$. We define then $$B= \bigcup_k B_k . $$ In Figure 1 there is an example of a set $B$ of simplices constructed according to this algorithm. \begin{figure} \centerline{\psfig{file=fig1.eps,height=5cm}} \caption{} \end{figure} For this example we have: $B_1= (153, 134, 142); \ B_2= (253,236,264);\ B_3=(356,364); \ B_4=(456)$. \medskip With the point $e_k$ we also associate the following set of chambers $B'_k$. In each simplex $\sigma$ let us choose one chamber\footnote{ In case of an affine plane in each simplex $\sigma$ there is only one chamber adjacent to the point $e_k$ since every edge of a chamber $\gamma \in \Gamma$ necessarily lies on some edge $q \in Q$.} adjacent to the point $e_k$. We define the set $B'_k$ as the set of all such chambers and define $$ B' = \bigcup_k B'_k.$$ \begin{figure} \centerline{\psfig{file=fig2.eps,height=5cm}} \caption{ (There is a mistake in the figure. One shaded chamber should be in a different place.)} \end{figure} In Figure 2 the chambers from the set $B'$ are shaded. \bigskip Suppose that we have described the construction in $V^{n-1}$. Let us describe it in $V^n$. \smallskip Let the points $e_i \in E$ be in $V^n$ and let $e_1, \ldots , e_N$ be an ordeing satisfying (\ref{conv}). Consider the point $e_k$ and the hyperplane $H_k$ from Lemma \ref{lemma}. In the hyperplane $H_k$ we have the set of points $E_k$ (see (\ref{EIK})), the set of simplices $\Sigma_k$ and the set of chambers $\Gamma_k$. Let us reorder the points $e^k_i$ so that the ordering $e^k_1, e^k_2, \ldots , e^k _{N_k}$ satisfies (\ref{conv}). By the induction hypothesis, we can construct a set of simplices in $H_k$, i.e. the set $\tilde{B}_k \subset \Sigma_k$ and the set of chambers in $H_k$, i.e. the set $\tilde{B}'_k \subset \Gamma_k$. Then we define the set $B_k$ of simplices in $V^n$ as $B_k= \{\mu(\sigma^k), \forall \sigma_k \in \Sigma _k\}$, where the map $\mu$ is defined by (\ref{mu}). Finally, we define $B=\bigcup_k B_k .$ \smallskip We have already constructed the set $\tilde{B}'_k$ of chambers in the hyperplane $H_k$. Consider $\gamma ^k \in \tilde{B}'_k$. According to the algorithm in $H_k$ the chamber $\gamma^k$ was chosen at a certain step $j, \ j \in (1, \ldots, N_k)$ and the point $e^k_j$ is a vertex of $\gamma^k$. Besides, there is one simplex $\sigma^k \in \tilde{B}_k$ such that $e^k_j$ is a vertex of $\sigma^k$ and $\gamma^k \subset \sigma^k$. Let us choose a chamber $\gamma \in \Gamma$ such that 1) $\gamma \subset \mu (\sigma^k) $ ; 2) $\gamma $ is adjacent to the point $e_k$ and to the edge $(e_k, e_j)$. Thus, with each chamber $\gamma^k \in \tilde{B}'_k$ we associate a chamber $\gamma \in \Gamma$. Denote by $B'_k$ the set of all such chambers $\gamma$ corresponding to $\gamma^k \in \tilde{B}'_k$ and define $$B'= \bigcup _k B'_k .$$ \smallskip In Figure 3 there is a fragment of a configuration of points in the 3-dimensional space. In the plane $H_k$, separating the points $e_1, \ldots, e_k$ and $e_{k+1}, \ldots , e_N$, there are five points which are reordered according to condition (\ref{conv}). For this ordering in the plane $H_k$ we construct the basis $$\tilde{B}_k= \{ (e_{i_1}e_{i_4} e_{i_5}),(e_{i_1}e_{i_5} e_{i_3}), (e_{i_1}e_{i_3} e_{i_2}); (e_{i_2}e_{i_4} e_{i_5}), (e_{i_2}e_{i_5} e_{i_3}); (e_{i_3}e_{i_4} e_{i_5})\}$$ of simplices and the basis $\tilde{B}'_k$ of chambers (are shaded). The set ${B}_k$ consists of the following simplices: $$B_k= \{ (e_k \bar{e}_{i_1} \bar{e}_{i_4}\bar{e}_{i_5}),\ (e_k \bar{e}_{i_1} \bar{e}_{i_5} \bar{e}_{i_3}), \ (e_k \bar{e} _{i_1} \bar{e}_{i_3} \bar{e}_{i_2});\ ( e_k \bar{e}_{i_2}\bar{e}_{i_4} \bar{e}_{i_5}),\ (e_k \bar{e}_{i_2} \bar{e}_{i_5} \bar{e}_{i_3});\ ( e_k \bar{e}_{i_3} \bar{e}_{i_4}\bar{e}_{i_5})\},$$ where $\bar{e}_j= \mu (e^k_j).$ \begin{figure} \centerline{\psfig{file=fig3.eps,height=9cm}} \caption{} \end{figure} Note that a chamber from $B'_k$ cannot be seen in Figure 3 since we need to take into account the points $e_1, \ldots, e_{k-1}$ which are below the plane $H_k$. \section{ Linear independence of simplices $\sigma \in B$ and linear independence of chambers $\gamma \in B'$.} Let $B \subset \Sigma$ and $B' \subset \Gamma$ be the sets constructed in Section 2. \begin{theorem} \label{indep} The simplices $\sigma \in B$ are linearly independent in $V_\Sigma$ and the chambers $\gamma \in B'$ are linearly independent in $V_\Gamma$. \end{theorem} First let us prove the following proposition. \begin{proposition} \label{block} Let $\tilde{A}$ be a submatrix of the incidence matrix $A$ corresponding to the rows $\sigma \in B$ and the columns $\gamma \in B'$. The columns and rows of the matrix $\tilde{A}$ can be ordered in such a way that: 1) $\tilde{A}$ is a block matrix $\parallel \cal{A}_{ik} \parallel $, where $\cal{A}_{ik}= 0$ for $i>k$, and 2) each diagonal element $a_{\sigma, \gamma}$ of the matrix $\tilde{A}$ equals $1$, i.e. $a_{\sigma, \gamma}=1.$ \end{proposition} {\bf Proof.} Let us recall that by the algorithm the set $B$ of simplices was constructed as $B=\cup B_k$ and the set $B'$ of chambers as $B'=\cup B'_k$, where $B_k, B'_k$ correspond to the point $e_k$ in the ordering $e_1, \ldots, e_N$. Thus, the matrix $\tilde{A}$ is a block-matrix $\parallel \cal{A}_{ik} \parallel$, where \begin{equation} \label{aik} \cal{A}_{ik}= \{ a_{\sigma, \gamma}, \ \sigma \in B_i, \ \gamma \in B'_k\}. \end{equation} Consider a diagonal block $\cal{A}_{kk}$ ($k=1, \ldots, N-n$). By the construction, to each simplex $\sigma \in B_k$ there corresponds a chamber $\gamma \in B'_k$ such that $\gamma \subseteq \sigma$, therefore, $a_{\sigma, \gamma}=1$. Thus, if we choose the corresponding orderings of columns in $B'_k$ and rows in $B_k$, we obtain $"1"$ on the main diagonal in the block $\cal{A}_{kk}$ and, therefore, any diagonal element $a_{\sigma, \gamma} $ of the matrix $\tilde{A}$ is such that $a_{\sigma, \gamma} =1$. \smallskip Consider a block $\cal{A}_{ik}$, where $i>k$. We need to prove that $a_{\sigma, \gamma}= 0$, where $\sigma \in B_i$ and $\gamma \in B'_k$. Let $\sigma \in B_i$ and $\gamma \in B'_1 \cup \ldots \cup B'_{i-1}$. Then $\sigma \in P_{i-1}=conv(e_i, \ldots, e_N)$. >From the algorithm for the construction of the set $B'$ it is easy to see that $\gamma \in S_1 \cup \ldots \cup S_{i-1}$. Due to formulas (\ref{decomp}) and (\ref{SP}) we conclude that $\gamma \not \subset \sigma$ and, therefore, $a_{\sigma, \gamma}=0$. Thus, the matrix $\tilde{A}$ is upper triangular as a block matrix. \qed \medskip {\bf Proof of Theorem \ref{indep}.} We will show that the submatrix $\tilde{A}$ defined above is an upper triangular matrix. Due to Proposition \ref{block} it is sufficient to prove that a block $\cal{A}_{kk}$ ( where $k=1, \ldots, N-n$) of the matrix $\tilde{A}$ is upper triangular. \smallskip Let us consider the case {\bf $n=2$}. Let $e_1, \ldots, e_N$ be an ordering satisfying (\ref{conv}). By the construction, the simplices $\sigma \in B_k$ lie between the neighbor edges starting at the point $e_k$, therefore, the open simplices $\sigma \in B_k$ are disjoint. Besides, there is exactly one chamber $\gamma \in B'_k$ (i.e. with the vertex $e_k$) such that $\gamma \in \sigma$, therefore, the block $\cal{A}_{kk}$ is the identity matrix. \medskip Since for a general $n$ the notations are cumbersome we consider in detail the case $n=3$ which already contains all the technique. Let $e_1, \ldots, e_N$ be an ordering satisfying (\ref{conv}). Consider a point $e_k$ and the block $\cal{A}_{kk}$ of the matrix $\tilde{A}$. We recall (see Section 2.3) that a simplex $\sigma \in B_k$ is defined as $\mu (\sigma^k)$, where the 2-dimensional simplex $\sigma ^k \in \tilde{B}_k$ lies in the plane $H_k$ separating the points $e_1, \ldots, e_k$ and $e_{k+1}, \ldots, e_N$. The set $\tilde{B}_k$ of simplices is constructed according to the algorithm in $H_k$. For this we order the points $e^k_i $ (see (\ref{EIK})) according to condition (\ref{conv}). Let $e^k_1, \ldots, e^k_{N_k}$ be such an ordering. Then $\tilde{B}_k= \bigcup _i \tilde{B}_{k,i}$, where $\tilde{B}_{k,i}$ is the set of 2-dimensional simplices which were chosen in the algorithm for the point $e^k_i$. We have a similar equality for chambers: $\tilde{B}'_k=\bigcup_i \tilde{B}'_{k,i}$, where $\tilde{B}'_{k,i}$ is the set of 2-dimensional chambers chosen in the algorithm for the point $e^k_i$. Due to the inductive construction of simplices $\sigma \in B_k$ and chambers $\gamma \in B'_k$ we obtain also the following formulas: $$B_k= \bigcup _i B_{k,i}$$ and $$B'_k=\bigcup_i B'_{k,i}.$$ This means that the block $\cal{A}_{kk}$ consists, in turn, of blocks $\cal{B}_{i_1, k_1}$: $$\cal{B}_{i_1,k_1}=\{a_{\sigma, \gamma}: \sigma^k \in \tilde{B}_{k,i_1}, \gamma^k \in \tilde{B}'_{k,k_1}\}, $$ where $\sigma = \mu(\sigma^k)$ and the chamber $\gamma$ corresponds \footnote{Note that in the algorithm there is no direct correspondence between the chambers $\gamma$ and $\gamma^k$; given a chamber $\gamma^k \subset H_k$ we find the corresponding simplex $\sigma^k \subset H_k$, then in the simplex $\sigma =\mu(\sigma^k)$ we choose a certain chamber (see Section 2.3).} to the chamber $\gamma^k \subset H_k$. \smallskip $1^0$. Consider a diagonal block $\cal{B}_{k_1,k_1}$ of the block $\cal {A}_{kk}$, i.e. all $a_{\sigma, \gamma}$, where $\sigma \in B_{k,k_1}$ and $\gamma \in B'_{k,k_1}$. Let $\sigma, \sigma_0 \in B_{k,k_1}$. Then the corresponding simplices $\sigma^k $ and $\sigma ^k_0$ were constructed on the plane $H_k$ from the same point $e^k_{k_1}$. By the algorithm the open simplices $\sigma^k,\sigma ^k_0$ are disjoint. Then (see Proposition \ref{prop1}) $\mu(\sigma^k) \cap \mu(\sigma^k_0) =\emptyset$, where $\mu $ is defined by formula (\ref{mu}). But $\sigma=\mu(\sigma^k)$, and $\sigma_0 =\mu(\sigma^k_0)$. Obviously, for any chamber $\gamma$ such that $\gamma \subset \sigma$, we have $\gamma \not \subset \sigma_0$. This means that the diagonal block $\cal{B}_{k_1,k_1}$ is the identity matrix. \medskip $2^0$. Let us show that $\cal{B}_{i_1,k_1}= 0$ for $i_1>k_1$. Indeed, let $\sigma \in B_{k,i_1}$ and $\gamma \in B'_{k,k_1}$. Then from the construction we have $\sigma^k \in \tilde{B}_{k,i_1}$ and $\sigma^k \in P^k_{i_1-1}=conv(e^k_{i_1}, \ldots, e^k_{N_k})$ (see (\ref{PS})). Concerning $\gamma$ we know that there is a simplex $\sigma_0 \in B_{k,k_1}$ such that: 1) $\gamma \in \sigma_0$; 2) $\gamma$ is adjacent to the point $e_k$; 3) $\gamma$ is adjacent to the edge $(e_k, e^k_{k_1})$. Since $\sigma_0 \in B_{k,k_1}$ we have $\sigma^k_0 \in \tilde{B}_{k,k_1}$ and $\sigma^k_0 \subset P^k_{k_1-1}$. For $i_1>k_1$ we can rewrite the formula (\ref{PK}) as follows: $$P^k= S^k_1 \cup \ldots \cup S^k_{k_1} \cup S^k_{k_1+1} \cup \ldots \cup S^k_{i_1-1}\cup P^k_{i_1-1},$$ where all the open polytopes $S^k_j$ and $P^k_{i_1-1}$ are disjoint. Note that if $i_1=k_1+1$ then $S^k_{k_1}=S^k_{i_1-1}$. Due to decomposition (\ref{tau}) we obtain $$\tau(P^k)= \tau(S^k_1) \cup \ldots \cup \tau(S^k_{k_1}) \cup \tau(S^k_{k_1+1}) \cup \ldots \cup \tau(S^k_{i_1-1})\cup \tau(P^k_{i_1-1}),$$ where all the corresponding open cones are disjoint. We have $\sigma= \mu(\sigma^k) \subset \tau(P^k_{i_1-1})$. \smallskip Let us show that $\gamma \subset \tau(S^k_{k_1})$. Since $\gamma \subset \sigma_0$, then $\gamma \subset \mu(\sigma^k_0)$, i.e. $\gamma \subset \ \tau(P^k_{k_1-1})$. Note that $P^k_{k_1-1}= S^k_{k_1} \cup S^k_{k_1+1} \cup \ldots$ (see formulas (\ref{PS}) and (\ref{PK})). Then $\gamma \subset \tau(S^k_{k_1}) \cup \tau(S^k_{k_1+1}) \cup \ldots.$ Any chamber $\gamma \in \Gamma$ may lie in only one of these cones. Since $\gamma $ is adjacent to the edge $(e_k, e^k_{k_1})$ we obtain $\gamma \subset \tau(S^k_{k_1})$. Then $\gamma \not \subset \tau(P^k_{i_1-1})$, i.e. $\gamma \not \subset \sigma$. We have proved that $a_{\sigma, \gamma}=0$ for $\sigma \in B_{k,i_1}$ and $\gamma \in B'_{k,k_1}$ if $i_1>k_1$. This completes the proof (for $n=3$) that the matrix $\tilde{A}$ is an upper triangular matrix. \bigskip In case of $n$-dimensional space an element $a_{\sigma, \gamma}$ of the matrix $\tilde{A}$ belongs to a sequence of enclosed blocks which can be denoted as $\cal{A}_{i_1,k_1}, \cal{B}_{i_2,k_2}, \cal{C}_{i_3,k_3}, \ldots$. (One can check that the "depth" of the enclosed blocks, i.e. the length of the sequence, is $n-1$.) $1^0.$ Let us show that a diagonal block of maximal depth is the identity matrix. Let $\cal{Z}_{k_{n-2}, k_{n-2}}$ be such a block. Then $\cal{Z}_{k_{n-2}, k_{n-2}}$ lies inside all diagonal blocks $\cal{A}_{k_0,k_0}, \cal{B}_{k_1,k_1}, \cal{C}_{k_2,k_2}, \ldots$ of the matrix $\tilde{A}$. Let $\sigma, \sigma_0$ be two simplices from the block $\cal{Z}_{k_{n-2},k_{n-2}}$. This means that $\sigma$ and $\sigma_0$ have the same sequence of corresponding points in the inductive construction. Let us denote these points by $e_{k_0}, e^{(1)}_{k_1}, e^{(2)}_{k_2}, \ldots, e^{(n-2)}_{k_{n-2}}$, where $e_{k_0}\in E$, $e^{(1)}_{k_1} \in H_{k_0}$, $e^{(2)}_{k_2}$ lies in the $(n-2)$-dimensional plane which corresponded to the point $e^{(1)}_{k_1}$ in the algorithm, and so on; finally, the point $e^{(n-2)}_{k_{n-2}}$ lies in the $2$-dimensional plane which corresponded to the point $e^{(n-3)}_{k_{n-3}}$. On this latter plane there are two simplices $\tilde{\sigma}, \tilde{\sigma_0}$ which were both chosen for the point $e^{(n-2)}_{k_{n-2}}$. According to the algorithm for the plane the open simplices $\tilde{\sigma}, \tilde{\sigma_0}$ are disjoint. Therefore (see Proposition \ref{prop1}), for the $3$-dimensional open simplices we have $\mu(\sigma) \cap \mu(\sigma_0) =\emptyset$, where $\mu$ is a map defined by formula (\ref{mu}) for the point $e^{(n-3)}_{k_{n-3}}$ instead of $e_k$. Then in order to obtain $4$-dimensional simplices, the map $\mu$ for the point $e^{(n-4)}_{k_{n-4}}$ was applied to the simplices $\mu(\sigma), \mu(\sigma_0)$ and so on. Finally, the map $\mu$ for the point $ e_{k_0}$ gives the simplices $\sigma , \sigma_0 \in \Sigma$. Clearly, we have $\sigma \cap \sigma_0 =\emptyset$. Therefore, for any chamber $\gamma \subset \sigma$ we have $\gamma \not \subset \sigma_0$, i.e. the block $\cal{Z}_{k_{n-2}, k_{n-2}}$ is the identity matrix. \medskip $2^0.$ In order to prove that the matrix $\tilde{A}$ is upper triangular it suffices to check that for $i>j$ any block $\cal{X}_{i,j} \in (\cal{B}_{i_1,k_1}, \cal{C}_{i_2,k_2}, \ldots) $ satisfies the condition $\cal{X}_{i,j}=0$. In Proposition \ref{block} we have proved that for $i>k$ a block $\cal{A}_{ik}=0$. By applying the arguments from $2^0$ of $n=3$ case, we can prove that in a diagonal block $\cal{A}_{kk}$ we have $\cal{B}_{{i_1},{k_1}}=0$ for $i_1>k_1$. Similarly, $\cal{C}_{{i_2},{k_2}}=0$ for $i_2>k_2$, etc. It follows from $1^0$ and $2^0$ that the submatrix $\tilde{A}$ of the incidence matrix $A$ is an upper triangular matrix. \qed \section{ The set $B$ is a geometrical basis of simplices.} In this section we will prove that the set $B$ constructed by the algorithm is a geometrical basis. First we repeat some of the definitions and theorems from \cite{AGZ} and \cite{A}. Let $E=(e_1, \ldots, e_N)$ be a set of points in the $n$-dimensional affine space $V^n$, $\Sigma$ the set of simplices and $\Gamma$ the set of chambers (defined in the Introduction). Consider a subset $S \subseteq E$ consisting of $n+2$ points and such that $S$ contains at least $n+1$ points in general position. Denote \begin{equation} \label{fsimpl} f = \{ \sigma: \sigma(e_{i_1}, \ldots, e_{i_{n+1}}) \in \Sigma \hbox{ and } e_{i_k} \in S \} \end{equation} Thus, with each $S$ we associate a subset $f\subset \Sigma$ (clearly, $f \neq \emptyset$). Let $F$ be the set of all such $f$ corresponding to all possible $S \subseteq E$. \begin{definition} We say that a point $p$ of affine space is visible from a point $e$, $e \neq p$, with respect to a simplex $\sigma$ if the open segment $(e,p)$ ia disjoint with $\sigma$, i.e. $(e,p) \cap \sigma =\emptyset $. We say also that a subset $S$ of points is visible from the point $e$ if every point of this subset is visible from $e$. \end{definition} \begin{theorem} \footnote{This theorem is stated in \cite{AGZ} in another form. Here we use the important geometric notion of visibility.} \label{TS} Let $\sigma \in \Sigma$ be a simplex and $e\in E $ a point that is not a vertex of $\sigma$. There is the following linear relation in $V_\Sigma$ among simplices: \begin{equation} \label{RelS} \sigma = \sum _{q_i \in Q^+} \sigma (q_i,e) - \sum _{q_i \in Q^-} \sigma (q_i,e), \end{equation} where $Q^+$ is the set of all facets (i.e. ($n-1$)-dimensional faces ) $q_i$ of the simplex $\sigma$ that are not visible from $e$ (with respect to $\sigma$); $Q^-$ is the set of all facets $q_i$ of the simplex $\sigma$ that are visible from $e$ (with respect to $\sigma$); $\sigma (q_i,e)$ is the $n$-dimensional simplex spanned by the facet $q_i$ of the simplex $\sigma$ and the point $e$. \end{theorem} \begin{definition} Let $B \subset \Sigma$. We say that an element $\sigma \not \in B$ is expressed in one step ``in terms of the set $B$ using $F$'' if there exists $f\in F$ such that $\sigma \in f, \ and \ f \setminus \sigma \subseteq B$. We say that an element $\sigma \not \in B$ can be expressed in $k$ steps in terms of the set $B$ using $F$ if there exists a sequence $\sigma_1, \ldots , \sigma_k,\ \sigma_i \in \Sigma,$ such that $\sigma_k=\sigma$ and $\sigma_1$ is expressed in one step in terms of the set $B$ (using $F$), $\sigma_2$ is expressed in one step in terms of the set $B \cup \sigma_1, \ldots , \ \sigma_k$ is expressed in one step in terms of the set $B\cup \sigma_1 \ldots \cup \sigma_{k-1}$. \end{definition} \begin{definition} A subset $B \subset \Sigma $ is a geometrical basis in $V_\Sigma$ with respect to $F$ if it satisfies the following conditions: 1) $B$ is a basis in $V_\Sigma$; 2) for any $\sigma \in \Sigma, \ \sigma \not \in B$ there exists $k$ such that $\sigma $ can be expressed in $k$ steps in terms of $B$ using $F$. \end{definition} Let $B \subset \Sigma$ be the set of simplices constructed by the algorithm of Section 1. \begin{theorem} \label{TS1} The set $B$ is a geometrical basis in $V_\Sigma$ with respect to the system $F$ defined by formula (\ref{fsimpl}). \end{theorem} {\bf Proof.} Due to Theorem \ref{indep} the simplices $\sigma \in B$ are linearly independent, therefore it is sufficient to prove that any simplex $\sigma \in \Sigma$ can be expressed in a finite number of steps in terms of $B$ with respect to the system $F$. This will be proved by induction on the dimension $n$ of the space $V^n$. {\bf Induction on $n$.} {\em First step ($n=2$).} The theorem is proved in \cite{AG}. \smallskip {\em Passing from $n-1$ to $n$.} Suppose that the statement is true for $V^{n-1}$. Let us prove it for $V^n$. Let the points $e_i \in E$ be in $V^n$ and an ordering $e_1, \ldots , e_N$ satisfy (\ref{conv}). Let us denote by $\Sigma^i$ the set of simplices $\sigma \in \Sigma$ such that $\sigma$ has the point $e_i$ as the vertex with the minimal number. We have \begin{equation} \label{sigma} \Sigma= \Sigma^1 \cup \ldots \cup \Sigma^{N-n}= \bigcup_{i=n}^{N-1} \Sigma^{N-i}, \end{equation} where $\Sigma^i \cap \Sigma^j=\emptyset,\ i\neq j$. We also have $\Sigma^N= \Sigma^{N-1}= \ldots = \Sigma^{N-n+1}=\emptyset$. The set $\Sigma^{N-n}$ either contains only one simplex $\sigma (e_N,e_{N-1}, \ldots, e_{N-n})$ or $\Sigma^{N-n}=\emptyset$. We need to prove that any simplex $\sigma \in \Sigma$ can be expressed in terms of $B$ using $F$. Due to the partition (\ref{sigma}) we can prove this statement by induction on $i$ considering cases when $\sigma \in \Sigma^{N-i}$, where $i=n, \ldots ,N-1$. {\bf Induction on $i$.} {\em First step.} Let us check the first nontrivial step of induction. Let $\Sigma^{N-i_0}$ (where $i_0 \geq n$) be the first nonempty set, i.e. $$\Sigma^{N-i_0}=\{ \sigma(e_N, \ldots , e_{N-i_0+1}, e_{N-i_0}) \},$$ where the points $e_N, \ldots , e_{N-i_0+1}$ lie in an $(n-1)$-dimensional hyperplane, while the point $e_{N-i_0}$ does not lie in this hyperplane. It is clear from the algorithm that the simplex $\sigma(e_N, \ldots , e_{N-i_0+1}, e_{N-i_0})$ belongs to the set $B_{N-{i_0}} \subset B$ and, therefore, can be expressed in terms of $B$ in $0$ steps. \medskip {\em Passing from $i-1$ to $i$.} Suppose that any simplex $\sigma \in \Sigma^{N-(i-1)}$ can be expressed in terms of $B$ using $F$. Let us show that any simplex $\sigma_0 \in \Sigma^{N-i}$ can also be expressed in terms of $B$ using $F$. \medskip Consider the point $e_{N-i}$ and the hyperplane $H=H_{N-i}$ of the algorithm. According to the algorithm we mark in $H$ the set $E_{N-i}$ of points $e_1^{N-i}, e_2^{N-i}, \ldots, e_{N_i}^{N-i}$, where $e_j^{N-i}=\overrightarrow{(e_{N-i},e_j)} \cap H$. To any vertex of $\sigma_0$ other than $e_{N-i}$, there corresponds a point from $E_{N-i}$, therefore, to the simplex $\sigma_0$ there corresponds one $(n-1)$-dimensional simplex $\sigma_0^{N-i}$ in $H$. Let $\Sigma_{N-i}$ be the set of all ($n-1$)-dimensional simplices with the vertices in $E_{N-i}$. We have $\sigma_0^{N-i} \in \Sigma_{N-i}$. Applying the algorithm in the hyperplane $H$, we construct the set $\tilde{B}_{N-i}$ of simplices, $\tilde{B}_{N-i} \subset \Sigma_{N-i}$. Due to the assumption of the induction on $n$, the simplex $\sigma_0^{N-i} \in \Sigma_{N-i}$ can be expressed in terms of $\tilde{B}_{N-i}$ using $F'$ (where $F'$ is the set of all subsets $f'$ defined in $H$ by formula (\ref{fsimpl}) ). \smallskip First, let us show that the simplex $\mu(\sigma_0^{N-i})$, where $\mu$ is the map defined by (\ref{mu}) for $k=N-i$, can be expressed in terms of $B$ using $F$. As we have proved, the simplex $\sigma^{N-i}_0$ can be expressed in terms of $\tilde{B}_{N-i}$ using $F'$ in a finite number of steps, for example, in $k$ steps. This means that there exists a sequence of simplices $\sigma_1^{N-i}, \ldots , \sigma_k^{N-i}$, where $\sigma_k^{N-i}= \sigma^{N-i}_0$ and a sequence of $f_1', \ldots , f_k ',\ \ f_i' \in F'$, such that \begin{equation} \label{first} f_1' \setminus \sigma_1^{N-i} \subseteq \tilde{B}_{N-i}, \end{equation} \begin{equation} \label{second} f_2' \setminus \sigma_2^{N-i} \subseteq (\tilde{B}_{N-i} \cup \sigma_1^{N-i}), \end{equation} $$ \ldots $$ \begin{equation} \label{last} f_k' \setminus \sigma_k^{N-i} \subseteq (\tilde{B}_{N-i} \cup \sigma_1^{N-i} \cup \ldots \cup \sigma_{k-1}^{N-i}). \end{equation} Consider formula (\ref{first}). It means that the simplex $\sigma_1^{N-i}$ can be expressed in terms of $\tilde{B}_{N-i}$ using $F'$. Let us show that this implies that the simplex $\mu(\sigma_1^{N-i})$ can be expressed in terms of $B_{N-i}$ using $F$. Indeed, according to the definition, the set $f'_1$ contains all the simplices with vertices in some $n+1$ points $e^{N-i} _{i_1}, \ldots, e^{N-i}_{i_{n+1}} \in E_{N-i}$. One of these simplices is $\sigma_1^{N-i}$. For simplicity of notations let us assume that $\sigma_1^{N-i}=\sigma( \widehat{e^{N-i}_{i_1}}, e^{N-i}_{i_2}, \ldots, e^{N-i}_{i_{n+1}}), $ where $\widehat{e}$ means that the point $e$ is not a vertex of the simplex. Thus, $f_1'$ consists of the following simplices: $$\sigma_1^{N-i}=\sigma( \widehat{e^{N-i}_{i_1}}, e^{N-i}_{i_2}, \ldots, e^{N-i}_{i_{n+1}}) ,$$ $$\sigma( e^{N-i}_{i_1}, \widehat{e^{N-i}_{i_2}}, \ldots, e^{N-i}_{i_{n+1}}) ,$$ $$\ldots$$ $$\sigma( e^{N-i}_{i_1}, e^{N-i}_{i_2}, \ldots, \widehat{e^{N-i}_{i_{n+1}}}), $$ where each simplex except $\sigma_1^{N-i}$ belongs to $\tilde{B}_{N-i}$ due to formula (\ref{first}). \smallskip To $f'_1 \in F'$ let us associate an element $f_1 \in F$. For this consider $n+2$ points $e_{N-i}, e^\mu _{i_1}, \ldots, e^\mu_{i_{n+1}} \in E$, where $e_j^\mu$ is the point of $E$ which is the closest to the point the point $e_{N-i}$ among all points of $E$ lying on the ray $\overrightarrow{(e_{N-i},e^{N-i}_j)}$. Then $f_1$ is the set of all simplices with the vertices in these $n+2$ points. Thus, $f_1$ consists of the following simplices: $$\sigma(e^\mu_{i_1}, e^\mu_{i_2}, \ldots, e^\mu_{i_{n+1}}) ,$$ $$\sigma(e_{N-i}, \widehat{e^\mu_{i_1}}, e^\mu_{i_2}, \ldots, e^\mu_{i_{n+1}}) ,$$ $$\sigma(e_{N-i}, e^\mu_{i_1}, \widehat{e^\mu_{i_2}}, \ldots, e^\mu_{i_{n+1}}) ,$$ $$\ldots$$ $$\sigma(e_{N-i}, e^\mu_{i_1}, e^\mu_{i_2}, \ldots, \widehat{e^\mu_{i_{n+1}}}). $$ The point $e_{N-i}$ is not the vertex of the simplex $\sigma(e^\mu _{i_1}, \ldots, e^\mu_{i_{n+1}}) $. Therefore, $\sigma(e^\mu _{i_1}, \ldots, e^\mu_{i_{n+1}}) \in \Sigma^{N-(i-1)}$. By induction hypothesis for $i$ this simplex can be expressed in terms of $B$ using $F$. Note that according to the algorithm, $$\sigma (e_{N-i}, e^\mu _{i_1}, \ldots, \widehat{e^\mu_{i_j}}, \ldots, e^\mu_{i_{n+1}}) =\mu (\sigma(e^{N-i}_{i_1}, \ldots, \widehat{e^{N-i}_{i_j}}, \ldots, e^{N-i}_{i_{n+1}}))$$ for any $j =1, \ldots, n+1$. Therefore, we have $$\sigma(e_{N-i}, \widehat{e^\mu_{i_1}}, e^\mu_{i_2}, \ldots, e^\mu_{i_{n+1}}) =\mu (\sigma^{N-i}_1).$$ Since each simplex $\sigma(e^{N-i}_{i_1}, \ldots, \widehat{e^{N-i}_{i_j}}, \ldots, e^{N-i}_{i_{n+1}}), \ j =2, \ldots, n+1$, belongs to $\tilde{B}_{N-i}$, each simplex $\sigma (e_{N-i}, e^\mu _{i_1}, \ldots, \widehat{e^\mu_{i_j}}, \ldots, e^\mu_{i_{n+1}})$ belongs to $B_{N-i}$ according to the construction of $B_{N-i}$. Thus, $f_1 \setminus \mu(\sigma_1^{N-i}) \subseteq (B_{N-i} \cup \sigma(e^\mu _{i_1}, \ldots, e^\mu_{i_{n+1}}),$ where, as we have already mentioned, the simplex $\sigma(e^\mu _{i_1}, \ldots, e^\mu_{i_{n+1}})$ can be expressed in terms of $B$ using $F$. We have proved that $\mu(\sigma_1^{N-i})$ can be expressed in terms of $B$ using $F$. \smallskip Considering consecutively formulas (\ref{second}) -- (\ref{last}) we can prove similarly that the simplex $\mu(\sigma_0^{N-i})$ can be expressed in terms of $B$ using $F$. \medskip Consider the simplex $\sigma_0$. The following cases are possible: 1) $\sigma_0= \mu(\sigma_0^{N-i})$; in this case the proof is already finished. 2) $\sigma_0 \neq \mu(\sigma_0^{N-i})$. Let $\sigma_0^{N-i}= \sigma(e_{j_1}^{N-i}, \ldots, e_{j_n}^{N-i})$. This case can only occur if there is a vertex of $\sigma_0$ which lies on some ray $\overrightarrow{(e_{N-i}, e_{j_k}^{N-i})},$ where $k\in (1, \ldots, n)$, and which is not the closest point from $E$ to the point $e_{N-i}$. Let us show that since the simplex $\mu (\sigma_0^{N-i})$ can be expressed in terms of $B$ using $F$ then the simplex $\sigma_0$ can be also expressed in terms of $B$ using $F$. For simplicity of notations let us denote here vertices of the simplices $\sigma_0$ and $\mu(\sigma_0^{N-i})$ as follows: $$\sigma_0=\sigma(e_{N-i},e_1^0, \ldots, e_n^0),$$ $$\mu(\sigma_0^{N-i})=\sigma(e_{N-i}, e_1^\mu, \ldots , e_n ^\mu).$$ We can also assume that in this notation the points $e_k^0$ and $e_k^\mu$ lie on the same ray $\overrightarrow{(e_{N-i}, e_{j_k}^{N-i})}$. First, let us consider the case when the simplices $\sigma_0$ and $\mu(\sigma_0^{N-i})$ differ only by one point, i.e. $e_k^0 \neq e_k^ \mu$ for some $k$ and we have $$\sigma_0= \sigma(e_{N-i}, e_1^\mu, \ldots, e_{k-1}^\mu, e_k^0, e_{k+1}^\mu, \ldots, e_n^\mu),$$ $$\mu(\sigma_0^{N-i})=\sigma(e_{N-i}, e_1^\mu, \ldots, e_{k-1}^\mu, e_k^\mu, e_{k+1}^\mu, \ldots, e_n^\mu).$$ Then for the $n+2$ points $e_{N-i}, e_1^\mu, \ldots, e_{k-1}^\mu, e_k^\mu, e_{k+1}^\mu, \ldots, e_n^\mu, e_k^0 \in E$ there exists $f \in F$ which consists of the following simplices: $$\sigma( e_{N-i}, e_1^\mu, \ldots, e_{k-1}^\mu, e_k^\mu, e_{k+1}^\mu, \ldots, e_n^\mu)=\mu(\sigma_0^{N-i}),$$ $$\sigma(e_{N-i}, e_1^\mu, \ldots, e_{k-1}^\mu, e_k^\mu, e_{k+1}^\mu, \ldots,e^\mu_{n-1}, e_k^0),$$ $$\ldots$$ $$\sigma(e_{N-i}, e_1^\mu, \ldots, e_{k-1}^\mu, e_k^\mu, e_k^0, \ldots, e_n^\mu)$$ $$\sigma( e_{N-i}, e_1^\mu, \ldots, e_{k-1}^\mu, e_k^0, e_{k+1}^\mu, \ldots, e_n^\mu)=\sigma_0,$$ $$\sigma(e_{N-i}, e_1^\mu, \ldots, e_k^0, e_k^\mu, e_{k+1}^\mu, \ldots, e_n^\mu),$$ $$\ldots$$ $$\sigma(e_{N-i}, e_k^0, \ldots, e_{k-1}^\mu, e_k^\mu, e_{k+1}^\mu, \ldots, e_n^\mu),$$ $$\sigma(e_k^0, e_1^\mu, \ldots, e_{k-1}^\mu, e_k^\mu, e_{k+1}^\mu, \ldots, e_n^\mu).$$ Since the points $e_{N-i}, e_k^0, e_k^\mu$ lie on the same ray $\overrightarrow{(e_{N-i}, e_{j_k})}$, all the simplices except $\sigma_0$ and $\mu(\sigma_0^{N-i})$ are not $n$-dimensional and do not belong to $\Sigma$. This implies that the simplex $\sigma_0$ can be expressed in terms of $B$ using $f \in F$. If the simplices $\sigma_0$ and $\mu(\sigma_0^{N-i})$ differ by two points, then we consider first a simplex $\sigma'$ which differs from the simplex $\mu(\sigma_0^{N-i})$ only by one point and express it in terms of $B$ using $F$. Then by applying the above arguments to the simplices $\sigma'$ and $\sigma_0$ we can express the simplex $\sigma _0$ in terms of $B$ using $F$. By repeating this process we prove that the simplex $\sigma_0$ can be expressed in terms of $B$ using $F$. Thus, the set $B$ constructed by the algorithm is a geometrical basis in $V_\Sigma$. \qed \smallskip A pair of a basis $e_1, \ldots, e_n$ in the space $V$ and a basis $f_1, \ldots, f_n$ in the dual space $V'$ is called a {\em triangular pair} if $(e_i, f_k)=0$ for $i>k$ and $(e_i,f_i)=1$. \smallskip Theorems \ref{TS1} and \ref{indep} imply \begin{theorem} The set $B'\subset\Gamma$ constructed by the algorithm is a basis in $V_\Gamma$. The basis of simplices $B$ and the basis of chambers $B'$ form a triangular pair. \end{theorem} \begin{thebibliography}{ 99} \bibitem{A} T.V.~Alekseyevskaya, {\em Combinatorial bases in systems of simplices and chambers}, Discrete Mathematics 157 (1996) 15--37. \bibitem{AG} T.V.~Alekseyevskaya, I.M.~Gelfand, {\em Incidence Matrices, Geometrical Bases, Combinatorial Prebases and Matroids}, will appear in Discrete Mathematics. \bibitem{AGZ} T.V.~Alekseyevskaya, I.M.~Gelfand, A.V.~Zelevinsky, {\em An arrangement of real hyperplanes and the partition function connected with it}, Soviet Math. Doklady 36 (1988) 589--593. \bibitem{DK} G.Danaraj, V.Klee, {\em Shellings of spheres and polytopes}, Duke Math. J., 41 (1974), 443-451. \end{thebibliography} \end{document}