Productos de permutaciones
Páginas: 2 (478 palabras)
Publicado: 2 de abril de 2011
Matrices de permutaciones
1. Objetivo. Vamos a conocer matrices de permutaciones, que se obtienen de la matriz identidad al intercambiar el orden de filas (o columnas). Estas matrices son importantespara la factorizaci´n PLU. o 2. Requisitos: Matrices elementales. Multiplicaci´n por matrices elementales. o Permutaciones. Descomposici´n de permutaciones en transposiciones. o 3. Definici´n (matrizde permutaci´n). Sea ϕ una permutaci´n, ϕ ∈ Sn . La matriz o o o de permutaci´n ϕ, denotada por Pϕ , se define mediante la f´rmula: o o Pϕ = (δϕ(i),j ) 1≤i≤n .
1≤j≤n
Es decir, en la i-´sima fila dela matriz Pϕ la ϕ(i)-´sima entrada es 1 y todas las dem´s e e a son 0. 4. Observaci´n. La i-´sima fila de la matriz Pϕ es igual a la ϕ(i)-´sima fila de la matriz o e e identidad. Por lo tanto, la matrizPϕ se obtiene de la matriz identidad al intercambiar el orden de filas. 5. Ejemplos. Para brevidad, vamos a usar la notaci´n corta de permutaciones. Es decir, o 1 2 3 4 en vez de escribiremos (3, 2,4, 1). 3 2 4 1 0 0 0 1 0 1 0 1 0 0 0 P(2,3,1) = 0 0 1 , P(4,1,3,2) = 0 0 1 0 . 1 0 0 0 1 0 0 6. Proposici´n (producto de matrices de permutaciones). o Pϕ Pψ = Pψϕ ∀ϕ, ψ ∈ Sn .7. Tarea adicional. Demuestre esta proposici´n, usando la defini´n formal de las matrices o o de permutaci´nes (a trav´s del s´ o e ımbolo de Kronecker).
−1 8. Corolario. Pϕ = Pϕ−1 para toda ϕ ∈ Sn .9. Matrices elementales de tipo ↔ son matrices de transposiciones. Una matriz elemental E↔ (i, j), donde i, j ∈ {1, . . . , n}, i < j, es la matriz de permutaci´n τi,j . Aqu´ τi,j o ı es latransposici´n de i y j. o E↔ (i, j) = Pτi,j . p´gina 1 de 2 a
10. Ejercicio. Matrices de permutaciones como productos de matrices elementales de tipo ↔. Demuestre que una matriz cuadrada es una matrizde permutaci´n si o y s´lo si se puede descomponer en el producto de matrices elementales de tipo ↔. o 11. Ejercicio. Calcule los productos P3,1,4,2 E↔ (1, 2) y E↔ (2, 3)P4,1,3,2 . 12. Ejercicio....
1. Objetivo. Vamos a conocer matrices de permutaciones, que se obtienen de la matriz identidad al intercambiar el orden de filas (o columnas). Estas matrices son importantespara la factorizaci´n PLU. o 2. Requisitos: Matrices elementales. Multiplicaci´n por matrices elementales. o Permutaciones. Descomposici´n de permutaciones en transposiciones. o 3. Definici´n (matrizde permutaci´n). Sea ϕ una permutaci´n, ϕ ∈ Sn . La matriz o o o de permutaci´n ϕ, denotada por Pϕ , se define mediante la f´rmula: o o Pϕ = (δϕ(i),j ) 1≤i≤n .
1≤j≤n
Es decir, en la i-´sima fila dela matriz Pϕ la ϕ(i)-´sima entrada es 1 y todas las dem´s e e a son 0. 4. Observaci´n. La i-´sima fila de la matriz Pϕ es igual a la ϕ(i)-´sima fila de la matriz o e e identidad. Por lo tanto, la matrizPϕ se obtiene de la matriz identidad al intercambiar el orden de filas. 5. Ejemplos. Para brevidad, vamos a usar la notaci´n corta de permutaciones. Es decir, o 1 2 3 4 en vez de escribiremos (3, 2,4, 1). 3 2 4 1 0 0 0 1 0 1 0 1 0 0 0 P(2,3,1) = 0 0 1 , P(4,1,3,2) = 0 0 1 0 . 1 0 0 0 1 0 0 6. Proposici´n (producto de matrices de permutaciones). o Pϕ Pψ = Pψϕ ∀ϕ, ψ ∈ Sn .7. Tarea adicional. Demuestre esta proposici´n, usando la defini´n formal de las matrices o o de permutaci´nes (a trav´s del s´ o e ımbolo de Kronecker).
−1 8. Corolario. Pϕ = Pϕ−1 para toda ϕ ∈ Sn .9. Matrices elementales de tipo ↔ son matrices de transposiciones. Una matriz elemental E↔ (i, j), donde i, j ∈ {1, . . . , n}, i < j, es la matriz de permutaci´n τi,j . Aqu´ τi,j o ı es latransposici´n de i y j. o E↔ (i, j) = Pτi,j . p´gina 1 de 2 a
10. Ejercicio. Matrices de permutaciones como productos de matrices elementales de tipo ↔. Demuestre que una matriz cuadrada es una matrizde permutaci´n si o y s´lo si se puede descomponer en el producto de matrices elementales de tipo ↔. o 11. Ejercicio. Calcule los productos P3,1,4,2 E↔ (1, 2) y E↔ (2, 3)P4,1,3,2 . 12. Ejercicio....
Leer documento completo
Regístrate para leer el documento completo.