Section07 Transposes and Permutations

$$\begin{array}{c} \begin{array}{ll} \boldsymbol{A} = \left[ \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{matrix} \right] & \boldsymbol{A}^{T} = \left[ \begin{matrix} a_{11} & a_{21} & \cdots & a_{m1} \\ a_{12} & a_{22} & \cdots & a_{m2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{mn} \\ \end{matrix} \right] \end{array} \\\\\\ \begin{array}{cl} \text{ Sum } & (\boldsymbol{A} + \boldsymbol{B})^{T} = \boldsymbol{A}^{T} + \boldsymbol{B}^{T}\\ \text{ Product } & (\boldsymbol{AB})^{T} = \boldsymbol{B}^{T} \boldsymbol{A}^{T}\\ \text{ Inverse } & (\boldsymbol{A}^{-1})^{T} = (\boldsymbol{A}^{T})^{-1} \end{array} \end{array}$$

• one perspective of $(\boldsymbol{AB})^{T} = \boldsymbol{B}^{T}\boldsymbol{A}^{T}$ $$\begin{array}{ll} & \text{Suppose the matrix } \boldsymbol{B} \text{ is a vector } \boldsymbol{x} \\ \therefore & \boldsymbol{Ax} \text{ is the linear combination of columns of matrix }\boldsymbol{A} \\ \therefore & (\boldsymbol{Ax})^{T} \text{ should be the linear combination of rows of matrix } \boldsymbol{A} \\ \therefore & \boldsymbol{x}^{T} \text{ should in the position before the matrix } \boldsymbol{A}^{T} \\ \therefore & (\boldsymbol{Ax})^{T} = \boldsymbol{x}^{T} \boldsymbol{A}^{T} \\ \end{array}$$

• proof of $(\boldsymbol{A}^{-1})^{T} = (\boldsymbol{A}^{T})^{-1}$ $$\begin{array}{ll} \because & \boldsymbol{AA}^{-1} = \boldsymbol{I} \\ \therefore & (\boldsymbol{AA}^{-1})^{T} = \boldsymbol{I}^{T} \\ \therefore & (\boldsymbol{A}^{-1})^{T} \boldsymbol{A}^{T} = \boldsymbol{I} \\ & \text{two sides times }(\boldsymbol{A}^{T})^{-1} \text{ at the same time.}\\ \therefore & (\boldsymbol{A}^{-1})^{T}\boldsymbol{A}^{T}(\boldsymbol{A}^{T})^{-1} = (\boldsymbol{A}^{T})^{-1} \\ \therefore & (\boldsymbol{A}^{-1})^{T} = ( \boldsymbol{A}^{T} )^{-1} \\ \end{array}$$

The Meaning of Inner Product

Symmetric Matrices

• Defination $$\begin{array}{cc} \boldsymbol{S}^{T} = \boldsymbol{S}\\ \textbf{OR} \\ s_{ij} = s_{ji} \end{array}$$

• the inverse of a symmetric matric is also symmetric. $$\begin{array}{c} \text{Suppose } \boldsymbol{S}^{T}= \boldsymbol{S} \text{, therefore} \\ (\boldsymbol{S}^{-1})^{T} = \boldsymbol{S}^{-1} \end{array}$$

Symmetric Products $\boldsymbol{A}^{T}\boldsymbol{A}$ and $\boldsymbol{AA}^{T}$ and $\boldsymbol{LDL}^{T}$

• proof of $\boldsymbol{A}^{T}\boldsymbol{A}$ and $\boldsymbol{AA}^{T}$ is symmetric. $$\begin{array}{ll} & \text{Suppose } \boldsymbol{C} = \boldsymbol{AA}^{T} \\ \therefore & \boldsymbol{C}^{T} = (\boldsymbol{AA}^{T})^{T} = (\boldsymbol{A}^{T})^{T} \boldsymbol{A}^{T} = \boldsymbol{AA}^{T} = \boldsymbol{C} \\ \therefore & \boldsymbol{AA}^{T} \text{ and } \boldsymbol{A}^{T}\boldsymbol{A} \text{ is symmetric.} \\ \end{array}$$
• If $\boldsymbol{S} = \boldsymbol{S}^{T}$ is factored into $\boldsymbol{LDU}$ with no row exchange, then $\boldsymbol{U}$ is excatly $\boldsymbol{L}^{T}$ (对称矩阵由一个对角线矩阵进行相同的行变化和列变化得到)

Permutation Matrices

• Defination

  • A permutation matrix $\boldsymbol{P}$ has the rows of the identity $\boldsymbol{I}$ in any order.

• Properties

  1. $\boldsymbol{P}^{-1}$ is also a permutation matrix.
  2. $\boldsymbol{P}^{-1}$ is always the same as $\boldsymbol{P}^{T}$ $$\boldsymbol{PP}^{T} = \boldsymbol{I}$$

The $\boldsymbol{PA} = \boldsymbol{LU}$ Factorization with Row Exchanges

Two possibilities

$\boldsymbol{PA} = \boldsymbol{LU}$

More Important!!

Row exchanges be done in advance. The row exchanges bring $\boldsymbol{A}$ to right order.

$\boldsymbol{A} = \boldsymbol{L_{1}P_{1}U_{1}}$

Hold row exchanges until after elimination.

Properties from Exercise

1. If matrix $\boldsymbol{S}$ is symmetric, then $\boldsymbol{PSP^{T}}$ ($\boldsymbol{P}$ is a permutation matrix) is also symetric.
   • proof $$( \boldsymbol{PSP}^{T} )^{T} = (\boldsymbol{P}^{T})^{T} \boldsymbol{S}^{T} \boldsymbol{P}^{T} = \boldsymbol{PSP}^{T}$$
2. $\boldsymbol{S} = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{A} \\ \boldsymbol{A}^{T} & \boldsymbol{0} \end{matrix} \right] = \boldsymbol{S}^{T}$
   • $\boldsymbol{S} = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{0} \\ \boldsymbol{A}^{T} & \boldsymbol{I} \end{matrix} \right] \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{0} \\ \boldsymbol{0} & -\boldsymbol{A}^{T}\boldsymbol{A} \end{matrix} \right] \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{A} \\ \boldsymbol{0} & \boldsymbol{I} \end{matrix} \right] = \boldsymbol{LDL}^{T}$
   • $\boldsymbol{S} \text{ is invetible } \Rightarrow \boldsymbol{A}^{T}\boldsymbol{A} \text{ is invertible.}$
     • Because the $\boldsymbol{L}$ and $\boldsymbol{L}^{T}$ is full of pivots, $\boldsymbol{D}$ is full of pivots, $\boldsymbol{A}^{T}\boldsymbol{A}$ is full of pivots, $\boldsymbol{A}^{T}\boldsymbol{A}$ is invertible.
   • $\boldsymbol{Ax} \ne \boldsymbol{0}$ whenever $\boldsymbol{x} \ne \boldsymbol{0}$
     • Because if exists $\boldsymbol{x} \ne \boldsymbol{0}$ make $\boldsymbol{Ax} = \boldsymbol{0}$, then must exsits the same $\boldsymbol{x} \ne \boldsymbol{0}$ make $\boldsymbol{A}^{T}\boldsymbol{Ax} = \boldsymbol{0}$, but $\boldsymbol{A}^{T}\boldsymbol{A}$ is invetible. Therefore, there isn't $\boldsymbol{x} \ne \boldsymbol{0}$ make $\boldsymbol{Ax} = \boldsymbol{0}$
3. if $A$ is a triangular matrix, $\boldsymbol{A}^{T}\boldsymbol{A}$ or $\boldsymbol{AA}^{T}$ is symetric.
4. Invertible symmetric matrices have symmetric inverse!
5. There are two permutation matrices $\boldsymbol{P}_{1}$ and $\boldsymbol{P}_{2}$
   • When permutation matrices $\boldsymbol{P}_{1}$ and $\boldsymbol{P}_{2}$ exchange a same row, $\boldsymbol{P}_{1}\boldsymbol{P}_{2} \ne \boldsymbol{P}_{2}\boldsymbol{P}_{1}$
   • When permutation matrices $\boldsymbol{P}_{1}$ and $\boldsymbol{P}_{2}$ exchange different row-pairs, $\boldsymbol{P}_{1}\boldsymbol{P}_{2} = \boldsymbol{P}_{2}\boldsymbol{P}_{1}$
6. $\boldsymbol{x} \cdot \boldsymbol{y} = \boldsymbol{Px} \cdot \boldsymbol{Py}$ ($\boldsymbol{P}$ is a permutation matrix)
7. northwest matrix
   • zero in southeast corner, below the antidiagonal.
   • Suppose $\boldsymbol{B}$ is a northwest matrix, $\boldsymbol{C}$ is a southeast matrix.
     • $\boldsymbol{B}^{T}$ is a northwest matrix.
     • $\boldsymbol{B}^{2}$ is a full matrix.
     • $\boldsymbol{B}^{-1}$ is a southeast matrix.
     • $\boldsymbol{BC}$ is a Upper triangular matrix.

Appendix

Perspective from derivative

$$\begin{array}{c} \boldsymbol{x}^{T}\boldsymbol{y} = (\boldsymbol{x}, \boldsymbol{y}) = \int_{-\infty}^{\infty}x(t)y(t) \cdot dt \\\\ \begin{array}{ll} & \text{Suppose Matrix } \boldsymbol{A} = \frac{d}{dt}\\ \therefore & (\boldsymbol{Ax}, \boldsymbol{y}) = \int_{-\infty}^{\infty}{\frac{dx(t)}{dt}y(t)\cdot dt} = \int_{-\infty}^{\infty}{x(t)\big(-\frac{dy(t)}{t}\big)}\cdot dt = (\boldsymbol{x}, \boldsymbol{A}^{T}\boldsymbol{y}) \\ \end{array} \end{array}$$