Show that matrices multiplication and LUP decompositions have the same difficulty Let $M(n)$ be the time to multiply two $n\times n$ matrices, and let $L(n)$ be the time to
compute the LUP decomposition of an $n\times n$ matrix.

How to show that multiplying matrices and computing LUP decompositions of matrices have essentially the same difficulty?
That is, we have to show that

*

*an $M(n)$-time matrix-multiplication algorithm implies an $O\left(M(n)\right)$-time LUP decomposition algorithm, and

*an $L(n)$-time LUP-decomposition algorithm
implies an $O\left(L(n) \right)$-time matrix multiplication algorithm.


 A: Let $A$ be an $n \times n$ matrix. Without loss of generality, assume $n$ is a power of 2. If $n$ is not a power of 2, we can always pad it with an identity matrix of size $k$:
$$
\left(\begin{array}{cc}
A & 0\\
0 & I_{k}
\end{array}\right)
$$
without affecting the asymptotic running time of the LUP factorization. We want to find matrices $P$, $L$, and $U$ such that $PA = LU$, $P$ is a permutation matrix (e.g. a permutation of the rows of $I$), $L$ is unit lower triangular (with ones on diagonal), and $U$ is upper-triangular (but not necessarily with ones on diagonal).
Now split $A$ into equal-sized blocks:
$$
A=\left(\begin{array}{cc}
B & C\\
D & E
\end{array}\right)
$$
Recursively perform a factorization $B = P_1 L_1 U_1$. We then have
$$
A   =\left(\begin{array}{cc}
P_{1} & 0\\
0 & I
\end{array}\right)\left(\begin{array}{cc}
L_{1}U_{1} & P_{1}^{T}C\\
D & E
\end{array}\right)
    =\left(\begin{array}{cc}
P_{1} & 0\\
0 & I
\end{array}\right)\left(\begin{array}{cc}
L_{1} & 0\\
DU_{1}^{-1} & E-DU_{1}^{-1}L_{1}^{-1}P_{1}^{T}C
\end{array}\right)\left(\begin{array}{cc}
U_{1} & L_{1}^{-1}P_{1}^{T}C\\
0 & I
\end{array}\right)
$$
Now perform a second factorization $E-DU_{1}^{-1}L_{1}^{-1}P_{1}^{T}C=P_{2}L_{2}U_{2}$. We then have
$$
A   =\left(\begin{array}{cc}
P_{1} & 0\\
0 & I
\end{array}\right)\left(\begin{array}{cc}
L_{1} & 0\\
DU_{1}^{-1} & P_{2}L_{2}U_{2}
\end{array}\right)\left(\begin{array}{cc}
U_{1} & L_{1}^{-1}P_{1}^{T}C\\
0 & I
\end{array}\right)
    =\left(\begin{array}{cc}
P_{1} & 0\\
0 & I
\end{array}\right)\left(\begin{array}{cc}
I & 0\\
0 & P_{2}
\end{array}\right)\left(\begin{array}{cc}
L_{1} & 0\\
DU_{1}^{-1} & L_{2}
\end{array}\right)\left(\begin{array}{cc}
U_{1} & L_{1}^{-1}P_{1}^{T}C\\
0 & U_{2}
\end{array}\right)
    =\left(\begin{array}{cc}
P_{1} & 0\\
0 & P_{2}
\end{array}\right)\left(\begin{array}{cc}
L_{1} & 0\\
DU_{1}^{-1} & L_{2}
\end{array}\right)\left(\begin{array}{cc}
U_{1} & L_{1}^{-1}P_{1}^{T}C\\
0 & U_{2}
\end{array}\right)
$$
Hence, $A = PLU$, where
$$
P=\left(\begin{array}{cc}
P_{1} & 0\\
0 & P_{2}
\end{array}\right),\;L=\left(\begin{array}{cc}
L_{1} & 0\\
DU_{1}^{-1} & L_{2}
\end{array}\right),\;U=\left(\begin{array}{cc}
U_{1} & L_{1}^{-1}P_{1}^{T}C\\
0 & U_{2}
\end{array}\right)
$$
Let $T(n)$ be the running time for this LUP factorization algorithm. I'll use $T(n)$ instead of $L(n)$ to reduce confusion with the $L$ matrix. We performed two recursive LUP factorizations on input size $n/2$, along with some matrix multiplications and inversions, both of which take time $M(n)$. Hence, the running time satisfies
$$
T(n)=2T(n/2)+O(M(n))
$$
Assuming $M(n)=\Omega(n^{2})$ and using the Master theorem or just performing the summation manually, we obtain the result $T(n)=O(M(n))$. QED
Remarks: 


*

*this question is actually exercise 28.2-2 in CLRS Intro to Algorithms 3ed, page 832.

*the $P$ matrix obtained in the method above may not be the same $P$ matrix as if we directly performed the LUP factorization. For this reason, it may not be the most optimal pivoting for numerical stability. The optimal pivoting obtained using direct LUP factorization does not appear to be separable into a nice block format for divide and conquer, although there is a much more involved method involving non-square LUP factorizations that does result in the same $P$.

*the statement in the other direction, which was present as of the 2nd printing of the third edition of CLRS, that given an LUP algorithm of time $L(n)$ we can perform matrix multiplication in the same amount of time was deleted from the book as an error. See the errata page. I haven't thought carefully about why they deleted it, but it's most likely because it's not true.

*proving that ordinary LU factorization, without the P, also takes the same time as multiplication is much more straightforward, and involves only elementary block matrix manipulation.
