\section{A Partitioned Matrix View of the Simplex Method}\label{S:Partitioned_Matrix_View_Simplex}
\setcounter{progress_ck_counter}{0}

\noi Partitioned matrices provide an elegant interpretation of the simplex algorithm in terms of matrix multiplication. This interpretation
is crucial for the development of ideas in subsequent sections.
\subsection{Partitioned Matrices}\label{SS:Partitioned_Matrices_Operations}
\newpar
Simply put, a \emph{partitioned matrix}\index{partitioned matrix} is a ``subdivision'' of a matrix into smaller submatrices or ``blocks,'' each obtained by deleting rows and/or columns of the original matrix. As a simple example, we consider the matrix $M$ defined by
\begin{equation}\label{E:partitioned_matrix_M}
M=\begin{bmatrix} 1 & 3 & 2 & 1 \\ 2 & 0 & -1 & 1 \\ -5 & 0 & 1 & 0 \\ 2 & 6 & 0 & 1 \end{bmatrix}.
\end{equation}

\newpar
Although $M$ has four rows and columns, it can be partitioned into four, 2-by-2 matrices. Namely,
if, $\ds A=\begin{bmatrix} 1 & 3 \\ 2 & 0 \end{bmatrix}$,
$\ds B=\begin{bmatrix} 2 & 1 \\ -1 & 1 \end{bmatrix}$,
$\ds C=\begin{bmatrix} -5 & 0 \\ 2 & 6 \end{bmatrix}$, and
$\ds I_2=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$, then

\begin{equation}\label{E:partitioned_matrix_ABCD}
M=\begin{bmatrix} A & B \\ C & I_2 \end{bmatrix}.
\end{equation}

\newpar
Clearly $M$ can be partitioned in different ways. However, the goal in most contexts
is to partition a matrix in a manner that facilitates performing matrix addition and/or multiplication.

\newpar
For example, the product $M^2$ can be calculated directly, but it can also be computed by using (\ref{E:partitioned_matrix_ABCD}) along with the fact all products
involving $A$, $B$, $C$, and $I_2$ are defined. The result is as follows:
\begin{align}\label{E:partitioned_matrix_M2_ABCD}
M^2 &=\begin{bmatrix} A & B \\ C & I_2 \end{bmatrix} \cdot \begin{bmatrix} A & B \\ C & I_2 \end{bmatrix}
 \\
&=\begin{bmatrix} A^2+BC & AB+BI_2 \\ CA+I_2C & CB+I_2^2 \end{bmatrix} \notag \\
&=\begin{bmatrix} A^2+BC & AB+B \\ CA+C & CB+I_2 \end{bmatrix} \notag
\end{align}

\newpar
Observe that we compute $M^2$ essentially by viewing each block as a scalar
and using the technique for multiplying 2-by-2 matrices. A simple calculation
shows that
(\ref{E:partitioned_matrix_M2_ABCD}), $\ds A^2+BC = \begin{bmatrix} -1 & 9 \\ 9 & 12 \end{bmatrix}$, which determines the four entries of $M^2$ belonging to the first two rows and first two columns. The
other three entries of (\ref{E:partitioned_matrix_M2_ABCD}) are computed in a similar manner.

\begin{progress_ck} Calculate each of the quantities
$\ds AB+B$, $\ds CA+C$, and $\ds CB+I_2$. Use the results to
compute the remaining entries of $M^2$. Then calculate $M^2$ directly using $M$ itself to verify that your
answer is correct.
\end{progress_ck}

\newpar
Care must be exercised when multiplying partitioned matrices so as to ensure that all products involving submatrices in the partition are defined and computed in the correct order.

\newpar
For example, suppose that $A$ and $B$ are 3-by-3 and 3-by-2 matrices, respectively.
Assume that $\vecc$ is a (column) vector in $\R^3$, $\vecd$ is a (row) vector in $\R^2$,
and that $\zerovec_{3\times1}$ and $\zerovec_{1\times3}$ represent the zero column vector and
zero row vector in $\R^3$, respectively. Then
$\ds \begin{bmatrix} A & \zerovec_{3\times 1} \\ \zerovec_{1\times 3} & 1 \end{bmatrix}$ and
$\ds\begin{bmatrix} B & \vecc \\ \vecd & 2 \end{bmatrix}$ are 4-by-4 and 4-by-3 matrices, respectively,
whose product is given by

\begin{align}\label{E:partitioned_matrix_unequal_size}
 \begin{bmatrix} A & \zerovec_{3\times 1} \\ \zerovec_{1\times 3} & 1 \end{bmatrix} \cdot
\begin{bmatrix} B & \vecc \\ \vecd & 2 \end{bmatrix}
&= \begin{bmatrix} AB+\zerovec_{3\times 1}\cdot \vecd & A\vecc +
2\cdot \zerovec_{3 \times 1} \\
\zerovec_{1\times 3}\cdot B +1\cdot \vecd & \zerovec_{1\times 3} \cdot \vecc+2 \end{bmatrix} \\
&= \begin{bmatrix} AB & A\vecc \\
\vecd & 2 \end{bmatrix}. \notag
\end{align}

\newpar
One means of ensuring various matrix products are defined is to record dimensions
of all matrices and vectors as subscripts.
For example, in (\ref{E:partitioned_matrix_unequal_size}), the entry, $AB+\zerovec_{3\times 1}\cdot \vecd $, can be
viewed as $A_{3\times 3}B_{3\times 2}+\zerovec_{3\times 1} \vecd_{1\times 2}$, all of whose products
and sums are defined and yield a 3-by-2 matrix.


\subsection{Partitioned Matrices with Maple}\label{SS:Partitioned_Matrices_Maple}
\index{partitioned matrix!constructed with Maple}


\noi Construction of partitioned matrices in Maple is very straightforward. Assume that matrices
\mf{A}, \mf{B}, and \mf{C} are defined using syntax discussed in Section \ref{S:Maple_Getting_Started_Linear_Algebra}. Matrices are augmented through use of the $|$ symbol and stacked using the comma. When augmentation and stacking are combined, the $<$ and $>$ signs are used
for grouping purposes. To produce the partitioned matrix (\ref{E:partitioned_matrix_ABCD}), we enter the
following:
\begin{maplelist}
\item \mf{A:=Matrix(2,2,[1,3,2,0]):}
\item \mf{B:=Matrix(2,2,[2,1,-1,1]):}
\item \mf{C:=Matrix(2,2,[-5,0,2,6]):}
\item \mf{I2:=IdentityMatrix(2):}
\item \mf{M:=<<A|B>,<C,I2>>;}
\end{maplelist}

\subsection{The Simplex Algorithm as Partitioned Matrix Multiplication}\label{SS:Partitioned_Matrices_View_of_Simplex}\index{simplex algorithm!via partitioned matrix multiplication}

\noi Partitioned matrices offer an important perspective from which to view the simplex algorithm. We
develop the main result by considering the \LP LP,

\begin{align}\notag
 \mbox{maximize } z &=\vecc \cdot \vecx  \label{E:Partitioned_Matrices_Matrix_Inequality_Form} \\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec, \notag
	\end{align}
where $\ds  \vecc=\begin{bmatrix} 4 & 3 \end{bmatrix}$,
$\ds A= \begin{bmatrix} 1 &  0 \\ 2 & 2 \\ 3 & 2 \end{bmatrix}$,
and $\ds \vecb= \begin{bmatrix} 8 \\ 28 \\32 \end{bmatrix}$.
The initial tableau, as discussed in Section \ref{S:Simplex}, is shown in Table
\ref{Ta:FuelPro_Initial_Tableau}.

\begin{table}[h]
\caption{Initial tableau for \LP LP}\label{Ta:FuelPro_Initial_Tableau}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline
1 & -4 & -3 & 0 & 0 & 0 & 0 \\ \hline
0 &  \fbox{1} & 0 & 1 & 0 & 0 & 8 \\ \hline
0 &  2 & 2 & 0 & 1 & 0 & 28 \\ \hline
0 &  3 & 2 & 0 & 0 & 1 & 32 \\ \hline
\end{tabular}
\end{table}

\noi
As a partitioned matrix, Table \ref{Ta:FuelPro_Initial_Tableau} is represented by
\begin{equation}\label{Ta:FuelPro_Initial_Partitioned_Matrix}
\begin{bmatrix} 1 & -\vecc & \zerovec_{1\times 3} & 0 \\
\zerovec_{3 \times 1} & A & I_3 & \vecb
\end{bmatrix}.
\end{equation}
\noi We refer to (\ref{Ta:FuelPro_Initial_Partitioned_Matrix}) as the \emph{tableau matrix}\index{tableau matrix}
corresponding to Table (\ref{Ta:FuelPro_Initial_Tableau}), and we label its rows and columns so that
the top row corresponds to row 0 and the leftmost column to column 0.


\newpar
At each iteration of the simplex algorithm, we pivot on an entry in the tableau matrix. As indicated by Table \ref{Ta:FuelPro_Initial_Tableau}, the initial pivot is on
the entry in row 1, column 1. The first row operation of this pivot
involves adding 4 times row 1 to row 0. If
we let $\vecy$ denote a 1-by-3 row vector in $\R^3$ whose $i$th entry corresponds to
the number of multiples of row $i$ added to row 0, then $\vecy=[4,0,0]$ records this first row operation. Moreover, after one iteration of
the simplex algorithm, the new row 0, in matrix form, is given by
\begin{equation}\label{E:partitioned_matrix_FuelPro_row0}
\left[ 1-\vecy \cdot \zerovec_{3 \times 1} \quad  -\vecc+\vecy A \quad \vecy \quad \vecy \vecb \right]
=\begin{bmatrix} 1 &  0 & -3 &  4 & 0 & 0 &  32 \end{bmatrix}.
 \end{equation}

 \begin{progress_ck}
 Verify that Equation (\ref{E:partitioned_matrix_FuelPro_row0}) is indeed correct.
 \end{progress_ck}

\newpar
The remaining row operations needed to perform the pivot involve subtracting twice row 1 from row 2 and then three times row 1 from 3. Each of these row operations can be performed separately on the identity matrix to obtain
$\ds E_1= \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$ and
$\ds E_2= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -3 & 0 & 1 \end{bmatrix}$, respectively.


\newpar
Matrices, $E_1$ and $E_2$, are examples of \emph{elementary matrices}\index{elementary matrix}, meaning that each is obtained by performing
a single elementary row operation on the identity matrix. A fundamental property of any elementary matrix, $E$, is that left multiplication of a matrix $B$ by $E$ performs on $B$ the elementary row operation corresponding to $E$. In the case of $E_1$ and $E_2$, left multiplication of $B$ by the product
$\ds M=E_2E_1=\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ -3 & 0 & 1 \end{bmatrix}$  has the overall effect of first subtracting twice row 1 from row 2 and then three times row 1 from 3. In a nutshell, when the submatrix of (\ref{Ta:FuelPro_Initial_Partitioned_Matrix})
obtained by deleting its top row is multiplied by $M$, the result obtained is precisely
that needed to complete the pivot of the first simplex iteration. In the form of partitioned matrix multiplication,
\begin{align}\notag
M \cdot \begin{bmatrix} \zerovec_{3 \times 1} & A & I_3 & \vecb \end{bmatrix} &=
\begin{bmatrix} M\cdot \zerovec_{3 \times 1} & MA & MI_3 & M\vecb \end{bmatrix} \notag \\
&= \begin{bmatrix} \zerovec_{3 \times 1} & MA & M & M\vecb \end{bmatrix} \notag \\
&= \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 8 \\
0 & 0 & 2 & -2 & 1 & 0 & 12\\
0 & 0 & 2 & -3 & 0 & 1 & 8 \end{bmatrix}. \label{E:partitioned_matrix_FuelPro_rows below}
\end{align}

\newpar
The results of (\ref{E:partitioned_matrix_FuelPro_row0}) and
(\ref{E:partitioned_matrix_FuelPro_rows below}) can now be in the following manner: We
construct a partitioned matrix whose first column consists
of $\ds \begin{bmatrix} 1  \\ \zerovec_{3 \times 1} \end{bmatrix}$, i.e., column 0 of the tableau matrix, which remains constant from one iteration to the next. We then augment this first column on the right by the matrix
$\ds \begin{bmatrix} \vecy \\ M \end{bmatrix}$, which results
in $\ds \begin{bmatrix} 1 & \vecy \\ \zerovec_{3 \times 1} & M \end{bmatrix}$. This matrix
is then right-multiplied by the original tableau matrix as follows:

\begin{equation}\label{E:partitioned_matrix_all_rows}
\begin{bmatrix} 1 & \vecy \\ \zerovec_{3 \times 1} & M \end{bmatrix}
\cdot
\begin{bmatrix} 1 & -\vecc  & \zerovec_{1\times 3} & 0 \\
\zerovec_{3 \times 1} & A & I_3 & \vecb\end{bmatrix} =
\begin{bmatrix} 1 & -\vecc+\vecy A & \vecy & \vecy\vecb \\
\zerovec_{3 \times 1} & MA & M & M\vecb \end{bmatrix} .
\end{equation}

\noi
The result of (\ref{E:partitioned_matrix_all_rows}) is the tableau matrix obtained
after one simplex algorithm iteration is applied to the \LP LP. A Maple worksheet
\textbf{Simplex Algorithm as Partitioned Matrix Multiplication.mw},
useful for verifying this fact is given as follows.

\begin{maplelist}
\item \mf{restart;with(LinearAlgebra):}
\item \mf{c:=Vector[row]([4,3]); \newline \# Create row vector with objective coefficients.}
\mo{c:=[4,3]}
\item \mf{A:=Matrix(3,2,[1,0,2,2,3,2]); \newline \# Matrix of constraint coefficients.}
\mo{A:=\begin{bmatrix} 1 & 0 \\ 2 & 2 \\ 3 & 2 \end{bmatrix}}
\item \mf{b:=<8,28,32>; \newline \# Constraint bounds.}
\mo{b:=\begin{bmatrix} 8 \\ 28 \\ 32 \end{bmatrix}}
\item \mf{TableauMatrix:=
\newline <<UnitVector(1,4)\vb <-c,A> \vb <ZeroVector[row](3),
IdentityMatrix(3)> \vb <0,b>>; 
\newline \# Create initial tableau matrix.}
\mo{TableauMatrix:=\begin{bmatrix}
1 & -4 & -3 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 8 \\
0 & 2 & 2 & 0 & 1 & 0 & 28 \\
0 & 3 & 2 & 0 & 0 & 1 & 32
\end{bmatrix}}
\item \mf{y:=[4,0,0];}
\mo{y:=Vector[row]([4,0,0])}
\item \mf{M:=Matrix(3,3,[1,0,0,-2,1,0,-3,0,1]);}
\mo{M:= \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\-3 & 0 & 1 \end{bmatrix}}
\item \mf{S:=<<<1>|y>,<ZeroVector(3)|M>>;
\newline \# Create partitioned matrix using y and M, which corresponds to first simplex iteration.}
\mo{ S:=\begin{bmatrix} 1 & 4 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -2 & 1 & 0 \\ 0 & -3 & 0 & 1 \end{bmatrix}}
\item \mf{S.TableauMatrix;
\newline \# Result after first iteration of simplex algorithm.}
\mo{\begin{bmatrix}
1 &0 &-3 & 4 & 0 & 0 & 32 \\
0 & 1 & 0 & 1 & 0 & 0 & 8 \\
0 & 0 & 2 & -2 & 1 & 0 & 12 \\
0 & 0 & 2 & -3 & 0 & 1 & 8
\end{bmatrix}}
\end{maplelist}

\newpar
We now consider
the second simplex iteration. Relabel $\vecy$ and $M$ in (\ref{E:partitioned_matrix_all_rows}) as
$\vecy_1$ and $M_1$. The second iteration introduces a new 3-by-1 vector, $\vecy_2$, and
a new 3-by-3 matrix, $M_2$, that record row operations needed to perform
the second iteration. The tableau matrix obtained after the second iteration
is then given as follows:

 \begin{multline}\label{E:partitioned_matrix_all_rows_second_iteration}
 \begin{bmatrix} 1 & \vecy_2 \\ \zerovec_{3 \times 1} & M_2 \end{bmatrix}\cdot
 \left(\begin{bmatrix} 1 & \vecy_1 \\ \zerovec_{3 \times 1} & M_1 \end{bmatrix}
\cdot
\begin{bmatrix} 1 & -\vecc  & \zerovec_{1\times 3} & 0 \\
\zerovec_{3 \times 1} & A & I_3 & \vecb \end{bmatrix} \right)  \\
=\left(\begin{bmatrix} 1 & \vecy_2 \\ \zerovec_{3 \times 1} & M_2 \end{bmatrix}\cdot
\begin{bmatrix} 1 & \vecy_1 \\ \zerovec_{3 \times 1} & M_1 \end{bmatrix}\right)
\cdot
\begin{bmatrix} 1 & -\vecc  & \zerovec_{1\times 3} & 0 \\
\zerovec_{3 \times 1} & A & I_3 & \vecb\end{bmatrix}   \\
=\begin{bmatrix} 1 & \vecy_1+\vecy_2M_1 \\ \zerovec_{3 \times 1} & M_2M_1 \end{bmatrix} \cdot
\begin{bmatrix} 1 & -\vecc  & \zerovec_{1\times 3} & 0 \\
\zerovec_{3 \times 1} & A & I_3 & \vecb \end{bmatrix}  \\
%=\begin{bmatrix} 1 & -\vecc+\vecy_1A+\vecy_2M_1A & \vecy_1+\vecy_2M_1 & \vecy_1\vecb +\vecy_2M_1\vecb \\
%\zerovec_{3 \times 1} & M_2M_1A & M_2M_1 & M_2 M_1 \vecb \end{bmatrix} \notag \\
= \begin{bmatrix} 1 & -\vecc+(\vecy_1+\vecy_2M_1)A & \vecy_1+\vecy_2M_1 & (\vecy_1 +\vecy_2M_1)\vecb \\
\zerovec_{3 \times 1} & M_2M_1A & M_2M_1 & M_2 M_1 \vecb \end{bmatrix}.
\end{multline}

\begin{progress_ck}
For the \LP LP, use the elementary row operations performed at the second iteration of the simplex
algorithm to verify that
\begin{equation}\label{E:partitioned_matrix_seconditeration_y_M}
\vecy_2=\begin{bmatrix} 0 & 0 & \frac{3}{2} \end{bmatrix} \quad \mbox{ and }
M_2=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & \frac{1}{2} \end{bmatrix}.
\end{equation}
Then combine these results with the previously computed values of $\vecy_1$ and $M_1$
to verify that (\ref{E:partitioned_matrix_all_rows_second_iteration})
coincides with the tableau matrix
corresponding to Table \ref{Ta:petroleum_third_tableau} from Section \ref{S:Simplex}.
\end{progress_ck}

\newpar
Clearly this process of expressing each tableau as a product of partitioned matrices continues to further iterations. We summarize the results in Theorem \ref{Th:Paritioned_Matrix_View_Simplex}.

\begin{theorem}\label{Th:Paritioned_Matrix_View_Simplex}\index{simplex algorithm!via partitioned matrix multiplication}
Consider the LP written in matrix inequality form as
\begin{align}\label{E:Partitioned_Matrices_Main_Theorem}
 \mbox{maximize } z &=\vecc \cdot \vecx  \notag\\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec, \notag
	\end{align}
where $A$ is an $m$ by $n$ matrix, $\vecc$ and $\vecx$ are row and column vectors, respectively, in $\R^n$, and $\vecb$ belongs to $\R^m$.
Row operations corresponding to the $k$th iteration of the simplex algorithm are characterized by left multiplication
using a partitioned (m+1) by (m+1) matrix of the form
\begin{equation}\label{E:Partitioned_Matrices_Main_Theorem_Multiplying_Matrix}
\begin{bmatrix} 1 & \vecy_k \\ \zerovec_{m \times 1} & M_k \end{bmatrix},
\end{equation}
where $\vecy_k$ is a row vector in $\R^m$ and $M_k$ is an $m$ by $m$ matrix.
The tableau matrix after the $k$th iteration is the corresponding
matrix after the $(k-1)^{\mbox{st}}$
iteration, left multiplied by (\ref{E:Partitioned_Matrices_Main_Theorem_Multiplying_Matrix}).
This inductive process leads to the following representation of the tableau matrix
resulting from the $k$th iteration:
\begin{multline}\label{E:Partitioned_Matrices_Main_Theorem_Multiplying_Partitioned_Matrix}
\begin{bmatrix} 1 & \vecy \\ \zerovec_{m \times 1} & M \end{bmatrix} \cdot \begin{bmatrix} 1 & -\vecc & \zerovec_{1\times m} & 0 \\
\zerovec_{m \times 1} & A & I_3 & \vecb
\end{bmatrix}
= \\
\begin{bmatrix} 1 & -\vecc+\vecy A & \vecy & \vecy\vecb \\ \zerovec_{m \times 1} & MA & M
& M \vecb \end{bmatrix},
\end{multline}
where
\begin{equation*}
M=M_k\cdot M_{k-1}\cdots M_1 \mbox{ and } \vecy=\vecy_1+\vecy_2 M_1 + \vecy_3 M_2 M_1+
\ldots +\vecy_k M_k M_{k-1} \cdots M_1.
\end{equation*}
\end{theorem}

\newpar
For the \LP LP, $\ds \vecy_1=\begin{bmatrix} 4 & 0 & 0 \end{bmatrix}$,
$\ds \vecy_2=\begin{bmatrix} 0 & 0 & \frac{3}{2} \end{bmatrix}$,
$\ds M_1=\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ -3 & 0 & 1 \end{bmatrix} $, and
$\ds M_2=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & \frac{1}{2} \end{bmatrix}$.
It then follows that for $k=2$,
\begin{align*}
\vecy &= \vecy_1 + \vecy_2 M_1 \\
&= \begin{bmatrix} 4 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & \frac{3}{2} \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ -3 & 0 & 1 \end{bmatrix} \\
&= \begin{bmatrix} -\frac{1}{2} & 0 & \frac{3}{2} \end{bmatrix}
\end{align*}
and
\begin{equation*}
M = M_2M_1 = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -\frac{3}{2} & 0 & \frac{1}{2} \end{bmatrix}.
\end{equation*}

\noi
Using these results, we can form the partitioned matrix
$\ds \begin{bmatrix} 1 & \vecy \\ \zerovec_{m \times 1} & M \end{bmatrix}$, which, in turn,
provides a means for determining the tableau matrix after the second iteration.

\newpar
At this stage, Theorem \ref{Th:Paritioned_Matrix_View_Simplex} is merely a theoretical result, one that does not affect the manner in which we perform the simplex algorithm. However, it demonstrates that
the quantities $\vecy$ and $M$ alone in  (\ref{E:Partitioned_Matrices_Main_Theorem_Multiplying_Partitioned_Matrix}) can be
used with an LP's initial tableau matrix to determine the entire tableau matrix at a given iteration. In the next section we exploit this fact and improve the efficiency of the simplex algorithm.

\section*{Exercises Section \protect\ref{S:Partitioned_Matrix_View_Simplex}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Partitioned_Matrix_View_Simplex}

\endinput 