La transposición de una matriz de permutación es su inversa.

Question

Esta es una pregunta del resumen gratuito de álgebra en línea de Harvard conferencias . Estoy publicando mis soluciones aquí para obtener algunos comentarios al respecto. Para una explicación más completa, véase este puesto.

Este problema es de la tarea 4.

Demostrar que la transposición de una matriz de permutación $P$ es su inversa.

Una matriz de permutación $P$ tiene un solo 1 en cada fila y un solo 1 en cada columna, siendo todas las demás entradas 0. Por tanto, la columna $j$ tiene un solo 1 en la posición $e_{i_jj}$ . $P$ actúa moviendo la fila $j$ a la fila $i_j$ para cada columna $j$ . Tomando la transposición de $P$ mueve cada 1 entrada de $e_{i_jj}$ a $e_{ji_j}$ . Entonces $P^t$ actúa moviendo la fila $i_j$ a la fila $j$ para cada fila $i_j$ . Como se trata de la operación inversa, $P^t=P^{-1}$ .

De nuevo, agradezco cualquier crítica a mi razonamiento y/o mi estilo, así como soluciones alternativas al problema.

Gracias.

Answer 1

Un cálculo directo también está bien: $$(PP^T)_{ij} = \sum_{k=1}^n P_{ik} P^T_{kj} = \sum_{k=1}^n P_{ik} P_{jk}$$ pero $P_{ik}$ suele ser 0, por lo que $P_{ik} P_{jk}$ suele ser 0. La única vez que $P_{ik}$ es distinto de cero es cuando es 1, pero entonces no hay ningún otro $i' \neq i$ tal que $P_{i'k}$ es distinto de cero ( $i$ es la única fila con un 1 en la columna $k$ ). En otras palabras, $$\sum_{k=1}^n P_{ik} P_{jk} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{otherwise} \end{cases}$$ y esta es exactamente la fórmula para las entradas de la matriz identidad, por lo que $$PP^T = I$$

Answer 2

Otra forma de demostrarlo es darse cuenta de que cualquier matriz de permutación es el producto de elemental permutaciones, donde por elemental Me refiero a una permutación que intercambia dos entradas. Ya que en una matriz identidad la permutación $i$ con $j$ en una fila es lo mismo que intercambiar $j$ con $i$ en una columna, dicha matriz es simétrica y coincide con su inversa. Entonces, suponiendo $P=P_1\cdots P_k$ con $P_1,\ldots,P_k$ elemental tenemos

$$ P^{-1} = (P_1\cdots P_k)^{-1}=P_k^{-1}\cdots P_1^{-1}=P_k\cdots P_1=P_k^t\cdots P_1^t = (P_1\cdots P_k)^t=P^t $$

Answer 3

Utilizando un poco de conocimiento sobre las matrices ortogonales la siguiente demostración es bastante sencilla:

Desde $v^tw=\sum_{k=0}^nv_iw_i$ si $v=(v_1,...,v_n),w=(w_1,...,w_n)$ tenemos $v^tv=1$ siempre que v sea una columna de $P$ . Por otro lado $v^tw=0$ si $v$ y $w$ son dos columnas distintas de $P$ . Por lo tanto, podemos concluir que $(P^tP)_{i,j}=\delta_{i,j}$ y así $P^t=P^{-1}$ .

Answer 4

Sea $π$ sea una permutación en $n$ objetos y

\begin{equation} \pi=\left(\begin{matrix} 1 & 2 &\ldots& n \\ \pi(1) & \pi(2) &\ldots& \pi(n) \end{matrix} \(derecha) \fin{ecuación}

Supongamos que $P_π$ sea una matriz de permutación. Tenemos que demostrar que $P_π^T P_π=I$ .

Tenga en cuenta que, $π$ envía el $i$ fila de la matriz identidad a la $π(i)$ fila, es decir,

\begin{eqnarray*} P_\pi=[P_{ij}]=\left\{ \begin{array}{ll} 1; & i=\pi(j)\\ 0; & i \ne \pi(j). \end{array} \Muy bien. \Fin.

En $ij$ ª componente de $P_\pi^TP_\pi$ es

\begin{eqnarray} (P_\pi^TP_\pi)_{ij}&=&\sum_{k=1}^n P^T_{ik}P_{kj}\\ &=&\sum_{k=1}^n P_{ki}P_{kj}\\ &=& P_{\pi(j)i}P_{\pi(j)j}\\ &=& P_{\pi(j)i}=\left\{ \begin{array}{ll} 1; & i=j\\ 0; & i \ne j. \end{array} \De acuerdo. \Fin.

Por lo tanto, $P^T_\pi P_\pi=I$ .

Answer 5

Si es menos sofisticado, podría simplemente sacarlo.

Primero, un lema:

La inversa de una matriz, si existe, es única.

Prueba: Si ambos $B$ y $C$ son inversos a $A$ entonces tenemos $B = BI = B(AC) = (BA)C = IC = C$ así que $B = C$ . (Aquí, $I$ denota la matriz de identidad).

De ello se desprende, en nuestro caso concreto, que para demostrar $A^t = A^{-1}$ sólo tenemos que mostrar $A^tA = A^t A = I$ .

Supongamos que $i\neq j$ . Entonces $(AA^t)_{ij} = \sum_k A_{ik}A^t_{kj} = \sum_k A_{ik}A_{jk}$ . Pero para cada $k$ , $A_{ik}A_{jk} = 0$ ya que sólo hay una entrada no nula en el $k$ la fila y $i\neq j$ (así $A_{ik}$ y $A_{jk}$ no puede ambos sea la entrada no nula). Por lo tanto, $(AA^t)_{ij} = 0$ cuando $i\neq j$ .

El argumento de que $(A^tA)_{ij} = 0$ cuando $i\neq j$ es casi idéntico, pero utiliza el hecho de que las columnas de $A$ contienen sólo una entrada no nula.

¿Puedes ver lo que sucede cuando, en su lugar, $i = j$ ?