where \(\{ \pi_0, \pi_1, \ldots ,
\pi_{n-1} \} \) is a permutation (rearrangement) of the integers \(\{ 0 , 1, \ldots , n-1 \} \text{,}\) we define the permutation matrix \(P( p )\) by
The last homework shows that applying \(P( p ) \) to a vector \(x \) rearranges the elements of that vector according to the permutation indicated by the vector \(p
\text{.}\)
Homework5.3.2.2.
Let
\begin{equation*}
p = \left( \begin{array}{c}
\pi_0 \\
\vdots \\
\pi_{n-1}
\end{array} \right)
\mbox{ and }
A = \left( \begin{array}{c}
\widetilde a_0^T \\
\vdots \\
\widetilde a_{n-1}^T
\end{array} \right).
\end{equation*}
The last homework shows that applying \(P( p ) \) to a matrix \(A \) rearranges the rows of that matrix according to the permutation indicated by the vector \(p
\text{.}\)
Homework5.3.2.3.
Let
\begin{equation*}
p = \left( \begin{array}{c}
\pi_0 \\
\vdots \\
\pi_{n-1}
\end{array} \right)
\mbox{ and }
A = \left( \begin{array}{c c c}
a_0 \amp \cdots \amp a_{n-1}
\end{array} \right).
\end{equation*}
\begin{equation*}
\begin{array}{l}
A P( p )^T \\
~~~=~~~~ \lt \mbox{ definition } \gt
\\
A
\left( \begin{array}{c}
e_{\pi_0}^T \\
\vdots \\
e_{\pi_{n-1}}^T
\end{array} \right)^T \\
~~~=~~~~ \lt \mbox{ transpose } P( p ) \gt
\\
A
\left( \begin{array}{c c c}
e_{\pi_0} \amp \cdots \amp
e_{\pi_{n-1}}
\end{array} \right) \\
~~~=~~~~ \lt
\mbox{ matrix-matrix multiplication by columns } \gt \\
\left( \begin{array}{c c c}
A e_{\pi_0} \amp \cdots \amp
A e_{\pi_{n-1}}
\end{array} \right) \\
~~~=~~~~ \lt A e_j = a_j \gt \\
\left( \begin{array}{c c c}
a_{\pi_0} \amp \cdots \amp
a_{\pi_{n-1}}
\end{array} \right)
\end{array}
\end{equation*}
The last homework shows that applying \(P( p )^T \) from the right to a matrix \(A \) rearranges the columns of that matrix according to the permutation indicated by the vector \(p
\text{.}\)
We will see that when discussing the LU factorization with partial pivoting, a permutation matrix that swaps the first element of a vector with the \(\pi\)-th element of that vector is a fundamental tool.
Definition5.3.2.2. Elementary pivot matrix.
Given \(\pi \in \{ 0, \ldots , n-1 \} \) define the elementary pivot matrix
where \(n \) is the size of the permutation matrix.
When \(\tilde P( \pi ) \) is applied to a vector, it swaps the top element with the element indexed with \(\pi \text{.}\) When it is applied to a matrix, it swaps the top row with the row indexed with \(\pi \text{.}\) The size of matrix \(\tilde P( \pi ) \) is determined by the size of the vector or the row size of the matrix to which it is applied.
In discussing LU factorization with pivoting, we will use elementary pivot matrices in a very specific way, which necessitates the definition of how a sequence of such pivots are applied. Let \(p\) be a vector of integers satisfying the conditions
\begin{equation}
p =
\left( \begin{array}{c}
\pi_0 \\
\vdots \\
\pi_{k-1}
\end{array}
\right), \quad \mbox{ where } \quad 1 \leq k \leq n
\mbox{ and } 0 \leq \pi_i \lt n-i,\label{chapter05-pivot-eqn-cond}\tag{5.3.1}
\end{equation}
then \(\widetilde P( p ) \) will denote the sequence of pivots
(Here \(\widetilde P( \cdot ) \) is always an elementary pivot matrix "of appropriate size.") What this exactly does is best illustrated through an example:
