\subsection{m x n Matrix}

The procedure developed in the previous section to zero out 
a sequence of elements in a 1 x $n$ vector can be extended to triangularize 
an arbitrary $m$ x $n$ matrix with $m \leq n$.
\footnote{For matrices with $m > n$, the triangularization procedure is
the same except that column vectors must be zeroed out (rather than row
vectors).}
The strategy is to zero out the rows of $A$ one at a time to obtain
a unit lower triangular matrix.

Let $A_{i}$ and $A'_{i}$ represent the $i$th row of the $m$ x $n$ matrices 
$A$ and $A'$, respectively.
The first step is to zero out entries in $A_{1}$, 
which can be done by employing \mbox{Algorithm~\ref{givens-1xn}}.  
Each row of matrix $A$ is multiplied by $\Psi _{1,j}$
  \[
	\left [ \begin{array}{c}
		A_{1} \\
		A_{2} \\
		\vdots  \\
		A_{m} 
		\end{array}
	\right ]
	\Psi _{1,j} =
	\left [ \begin{array}{c}
		A^{'}_{1} \\
		A^{'}_{2} \\
		\vdots  \\
		A^{'}_{m} 
		\end{array}
	\right ].
  \]
The equation $A_{1} \Psi _{1,j} = A^{'}_{1}$ is Equation~\ref{APsiA}
with $i$=1.
The remaining row transformations can be represented by
  \begin{equation}
	[a_{k1} \ldots a_{kj} \ldots a_{kn}] \Psi _{1,j} =
	[a^{'}_{k1} \ldots a^{'}_{kj} \ldots a_{kn}],
     \label{AkPsiAk}
  \end{equation}
where $a_{kj}$ and $a'_{kj}$ represent the $j$th elements of $A_{k}$
and $A'_{k}$, respectively.  Only elements
1 and $j$ of $A_{k}$ change, given by
  \begin{equation}
	a^{'}_{k1} = \frac{a_{11}d_{1}}{d^{'}_{1}}a_{k1} +
			\frac{a_{1j}d_{j}}{d^{'}_{1}}a_{kj}
     \label{pre-a'k1}
  \end{equation}
  \begin{equation}
	a^{'}_{kj} = - a_{1j}a_{k1} + a_{11}a_{kj}.
     \label{pre-a'kj}
  \end{equation}

For $A_{i}$, we need to compute $\Psi _{i,j}$ for all $j > i$ 
in order to complete the matrix triangularization.  
When zeroing $A_{i}$, Equations~\ref{pre-a'k1}~and~\ref{pre-a'kj}
become
  \begin{equation}
	a^{'}_{ki} = \frac{a_{ii}d_{i}}{d^{'}_{i}}a_{ki} +
			\frac{a_{ij}d_{j}}{d^{'}_{i}}a_{kj}
     \label{a'ki}
  \end{equation}
  \begin{equation}
	a^{'}_{kj} = - a_{ij}a_{ki} + a_{ii}a_{kj}.
     \label{a'kj}
  \end{equation}
Note that all rotations of $A_{i}$ affect all other rows.  
However, each row above $A_{i}$
contains zeroes as $i$th and $j$th elements, and as evidenced by
Equations~\ref{a'ki}~and~\ref{a'kj}, these elements will remain as zeroes
for any rotation applied to them.  

A procedure to triangularize the $m$ x $n$ matrix $A$ using fast
Givens rotations is summarized in
Algorithm~\ref{givens-mxn}.  Row $A_{1}$ is first zeroed out, then $A_{2}$,
and so on until a unit lower triangular matrix is achieved by zeroing
out all rows of $A$.
The order in which the elements of $A$ are zeroed out can affect the 
efficiency of the algorithm.

\begin{algorithm}
\begin{tabbing}
For \= For \= For \= each $A_{k}$ below $A_{i}$ ($i < k \leq m$) \= \kill
For each row $A_{i}$ of $A$ ($i=1,\ldots,m$) \\
\> For each element $j$ of $A_{i}$ ($j=n,\ldots,i+1$) \\
\> \> Calculate $d^{'}_{i}$ \> \> [Equation \ref{d'i}] \\
\> \> Calculate $d^{'}_{j}$ \> \> [Equation \ref{d'j}] \\
\> \> Calculate matrix $\Psi _{i,j}$  \> \> [Equation \ref{Psiij}] \\
\> \> Calculate $A^{'}_{i}$, the rotation of $A_{i}$
					 \> \> [Equation \ref{APsiA}] \\
\> \> \\
\> \> For each $A_{k}$ below $A_{i}$ ($k=i+1,\ldots,m$) \\
\> \> \> Calculate $a^{'}_{ki}$ \> [Equation \ref{a'ki}] \\
\> \> \> Calculate $a^{'}_{kj}$ \> [Equation \ref{a'kj}] \\
\> \> \> Reset $A_{k}$ to $A^{'}_{k}$ \> \\
\> \> EndFor \\
\> \> \\
\> \> Reset $A_{i}$ to $A^{'}_{i}$ \> \\
\> \> Reset $D$ to $D^{'}$ \> \\
\> EndFor \\
EndFor 
\end{tabbing}
\caption{Fast Givens Rotations: $m$ x $n$ matrix}
\label{givens-mxn}
\end{algorithm}


