GEOMETRIA ANALITICA Y ALGEBRA

SEMANA 13: TEORÍA ESPECTRAL-VALORES Y VECTORES PROPIOS

Mg. Dennis Quispe Sánchez

 CASO APLICATIVO

El número cromático de un grafo se define como el numero mínimo de colores necesarios para
colorear los vértices de la grafica de modo que dos vértices adyacentes no tengan asignado el
mismo color. Los vértices son adyacentes si están conectados por una arista.

La matriz de adyacencia de una grafica es simétrica, entonces, los valores característicos 𝜆 serán
valores reales y por lo tanto, se pueden ordenar de mayor a menor.

Suponga que la gráfica es conexa; es decir, existe una trayectoria de cada vértice a cualquier
otro, quizá a través de otros vértices. Sea 𝜒 el numero cromático. Entonces se puede demostrar
que

Donde 𝜆1 es el mayor autovalor y 𝜆𝑛 el menor.

 CASO APLICATIVO
Usando este teorema, encuentre cotas sobre el número cromático para el grafo de Petersen.
Verifique el resultado volviendo a dibujar las graficas y pintando los vértices con los colores
adecuados.
LOGRO

Al término de la sesión, el
estudiante determina, los valores
y vectores propios, polinomio
característico de una matriz,
usando las propiedades de estas
matrices en la resolución de
ejercicios y/o problemas
vinculados a la ingeniería,
siguiendo un proceso ordenado e
interpretando los resultados.
AUTOVALORES Y AUTOVECTORES
POLINOMIO Y ECUACION CARACTERISTICA
 EJEMPLO
2 −12
Determinar los eigenvalores y eigenvectores de la matriz 𝐴 =
1 −5
SOLUCION
 EIGENESPACIO O ESPACIO PROPIO

Sea 𝝀 un valor característico de la matriz A de orden n x n, entonces el

subespacio:
𝐸𝜆 = 𝑣: 𝐴𝑣 = 𝜆𝑣
Es el eingenespacio o espacio propio correspondiente al valor característico λ.
 EJEMPLO

Determinar los autovalores y auto vectores de la matriz:

¿Cuál es la dimensión del espacio propio de cada autovalor?

SOLUCION
 MULTIPLICIDAD ALGEBRAICA Y GEOMETRICA
La multiplicidad algebraica de un eigenvalor es como su multiplicidad como una raíz de la
ecuación característica

La multiplicidad geométrica de un eigenvalor λ se define como dim Eλ , la dimensión de su

correspondiente eigenespacio.

𝜎 𝐴 = 𝜆: 𝜆 𝑒𝑠 𝑢𝑛 𝑎𝑢𝑡𝑜𝑣𝑎𝑙𝑜𝑟 = 𝑒𝑠𝑝𝑒𝑐𝑡𝑟𝑜 𝑑𝑒 𝐴

𝜌 𝐴 = 𝑚𝑎𝑥 𝜆𝑖 : 𝜆𝑖 ∈ 𝜎(𝐴) = 𝑟𝑎𝑑𝑖𝑜 𝑒𝑠𝑝𝑒𝑐𝑡𝑟𝑎𝑙

EJEMPLO
 EJEMPLO

1. Sea 𝑇: 𝐶 ′ [0,1] → 𝐶[0,1] definida por 𝑇𝑓 = 𝑓′. Demuestre que 𝜆 = 1 es un eigenvalor de T

con su correspondiente eigenvector 𝑓 𝑥 = 𝑒 𝑥 .

2. Sea 𝑇: 𝑃2 → 𝑃2 definida por 𝑇 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 = −3𝑎1 + 5𝑎2 + (−4𝑎0 + 4𝑎1 −

10𝑎2 )𝑥 + 4𝑎2 𝑥 2 . Determine los eingenvalores y eigenvectores de T asociados a la base usual.
 EJEMPLO

1. ¿Cuáles son los posibles eigenvalores de una matriz idempotente? (Recuerde que una matriz
cuadrada A es idempotente cuando 𝐴2 = 𝐴).
2. ¿Cuáles son los posibles eigenvalores de una matriz nilpotente? (Recuerde que una matriz
cuadrada A es nilpotente si existe un entero positivo k tal que 𝐴𝑘 = 0).
3. Para una matriz invertible A demuestre que A y 𝐴−1 tienen los mismos eigenvectores. ¿cómo
se relacionan los eigenvalores de A con los eigenvalores de 𝐴−1 ?
4. Demuestre que A y 𝐴𝑇 tienen los mismos eigenvalores. ¿Los eigenespacios son iguales?
 APLICACION A LA TEORIA DE GRAFOS

POLINOMIO CARACTERISTICO:
Sea G un grafo con n vértices (sin lazos ni aristas múltiples) y A su matriz de adyacencia.
Definimos el polinomio característico de G como 𝑝𝐺 𝜆 = 𝜆𝐼 − 𝐴 .

Ejemplo: Consideraremos ahora el grafo diamante, calcularemos su polinomio característico.

Para ello, en primer lugar, necesitaremos su matriz de adyacencia asociada.

Entonces, el polinomio característico de G es:

𝜆 −1 0 − 1
𝑝𝐺 𝜆 = 𝜆𝐼 − 𝐴 = −1 𝜆 −1 − 1 = 𝜆4 − 5𝜆2 − 4𝜆
0 −1 𝜆 − 1
−1 − 1 − 1 𝜆
 APLICACION A LA TEORIA DE GRAFOS

AUTOVALOR DE UN GRAFO:
Decimos que 𝜆 es un autovalor del grafo G si es raíz de su polinomio característico 𝑝𝐺 𝜆 .

En el ejemplo anterior:

Los autovalores del grafo son:

𝜆1 = 2,56155; 𝜆2 = 0; 𝜆3 = −1; 𝜆4 = −1,56155

En lo que sigue del capítulo siempre consideraremos los autovalores 𝜆1 , 𝜆2 , … . . 𝜆𝑛 ordenados de

manera estrictamente decreciente.
 APLICACION A LA TEORIA DE GRAFOS

PROPOSICION: Sea G un grafo con n vértices y m aristas, y

su polinomio característico. Entonces los coeficientes de 𝑝𝐺 (𝜆) satisfacen:

1. 𝑎1 = 0
2. -𝑎2 = 𝑚
3. -𝑎3 = 2𝑡, siendo t el número de triángulos de G.

3 ≤ 𝜌(𝐺) ≤ 3
 APLICACION A LA TEORIA DE GRAFOS

COLORACION DE UN GRAFO:
Sea G = (V;E) un grafo simple y S el conjunto de colores de la colección {c1, c2, c3,…,cn}. Una
coloración de los vértices de G con los colores de S es una correspondencia tal que a cada uno
de los vértices de G se le asigna un color de S de manera que dos vértices adyacentes no pueden
recibir el mismo color.
EJEMPLO: Una 4 coloración

Sin embargo, es fácil ver que este grafo puede ser coloreado también con tres colores
(coloreando con 1(rojo) el vértice coloreado con 4 (amarillo)), que es el mínimo número de
colores con el que lo podemos colorear. Esto es lo que se entiende por número cromático de un
grafo.
 APLICACION A LA TEORIA DE GRAFOS

NUMERO CROMATICO:
Se define el número cromático de un grafo G como el menor valor 𝑘 ∈ ℕ tal que G es k
coloreable y se denota por 𝜒(𝐺). Si 𝑘 = 𝜒(𝐺) se dice que el grafo G es k-cromático.
Del ejemplo anterior el grafo G es 3-cromático, 𝜒 𝐺 = 3.

El Teorema de los cuatro colores establece que todo mapa geográfico con regiones continuas puede ser
coloreado con cuatro colores diferentes de forma que no queden regiones adyacentes con el mismo color.
Además del problema de los cuatro colores hay muchos otros que pueden resolverse mediante la coloración
de un grafo de forma similar. Por ejemplo, el almacenamiento de productos químicos donde hay
determinados productos que son incompatibles entre sí y, por lo tanto, deben almacenarse de manera
independiente; o distribuir las especies de animales de un zoológico teniendo en mente que hay especies
que no pueden cohabitar en un mismo territorio.
 APLICACION A LA TEORIA DE GRAFOS

TEOREMA:
Suponga que la gráfica es conexa; es decir, existe una trayectoria de cada vértice a cualquier
otro, quizá a través de otros vértices. Sea 𝜒 el número cromático. Entonces se cumple que:

2,56155
1− ≤ 𝜒 𝐺 ≤ 1 + 2,56155
−1,56155

2,64 ≤ 𝜒 𝐺 ≤ 3,56155

𝜒 𝐺 =3
TEORÍA DE PERRON-FROBENIUS: IMPORTANCIA, PODER Y
CENTRALIDAD
Si tenemos una red social en la que varios individuos interactúan (ya sea a través de relaciones
de amistad, sentimentales, laborales o de cualquier otro tipo), ¿podemos medir de alguna
manera la influencia o centralidad de cada nodo en el resto de la red social?

Para responder a esta pregunta, emplearemos un modelo matemático en el que una red social
se interpreta como una red compleja G = (X,E) en la que cada nodo es uno de los individuos de
la red, y si entre dos individuos i, j se produce una interacción social (ya sea una relación de
amistad, sentimental, laboral o de cualquier otro tipo), entonces hay una arista entre ellos en el
grafo G.

La red compleja que se asocia a una red social puede ser tanto no dirigida como dirigida,
dependiendo de la tipología concreta de interacción social que se tenga. Así, por ejemplo, la red
social Facebook es no dirigida (las relaciones de amistad entre individuos en esta red social son
recíprocas, por lo que las aristas de G son no dirigidas), mientras que Twitter se modela con una
red dirigida (en este caso la interacción social es ser seguidor de, que puede ser no recíproca) y
por tanto las aristas de G son dirigidas, de forma que i ! j quiere decir que el individuo i es
seguidor de j.
TEORÍA DE PERRON-FROBENIUS: IMPORTANCIA, PODER Y
CENTRALIDAD
 TEORÍA DE PERRON-FROBENIUS: IMPORTANCIA, PODER Y
CENTRALIDAD

Teniendo en cuenta que el conjunto X es finito (y tiene tamaño n ∈ N), encontrar una función
c(·) que cumpla lo anterior es equivalente a definir un vector c = (c1, . . . , cn) ∈ 𝑅𝑛 de forma que
f(i) = ci (la componente i-ésima del vector c) para cada 1 ≤ i ≤ n. Una función f de este tipo se
denomina medida de centralidad y existen diferentes formas alternativas de definir este tipo de
funciones en sociología matemática, en particular, y en el análisis de redes complejas, en
general, dependiendo del tipo de red que se considere.
 APLICACION DE LA TEORIA DE PERRON-FROBENIUS

Suponga que consideramos la siguiente red como la representación de las rutas de líneas aéreas
de American Airlines entre las capitales 1. Dublín, 2. Estocolmo, 3.Moscu, 4.Londres, 5. Berlín, 6.
Kiev, 7. Paris y 8. Roma. Una compañía desea elegir una ciudad para localizar su oficina matriz.
Después de analizar la grafica, escriba un informe al director de la compañía con su
recomendación (y justificación).

1. Hallar el espectro de A y elegir el mayor autovalor.

2. Hallar el auto vector v asociado a este autovalor.
3. Hallar la norma 1 del vector v.
4. Hallar el vector 𝑐 𝑖 = 𝑓 𝑖 de centralidad Bonacich, determinar la influencia o centralidad
de cada ciudad.
 SOLUCION

1) Para el grafico de ruta de la aerolínea la matriz de adyacencia es:

Calculamos el espectro de A

𝜎 𝐴 = −2.52826, −1.83274, −0.91409, −0.20042, 0.37278, 0.79363, 1.34205, 2.96704

𝜆8 = 2.96704 = 𝜌(𝐴)
 SOLUCION

2) Hallar el vector propio 𝑣8 asociado al mayor valor propio 𝜆8 :

𝑣8 =

3) Hallamos la norma 1 del vector 𝑣8 ; 𝑣8 1 = 0.15077 + ⋯ + 0.34269 = 2.72831

4) Hallamos el vector de centralidad Bonacich:

𝑣8
𝑐= = Ciudad 4
𝑣8 1
 SOLUCION

5) Informe redacción y conclusiones

La ciudad 4. Londres conecta directamente a mas ciudades (Dublín, Paris, Estocolmo y Moscú)
que cualquier otra ciudad. Aquí debería de localizarse la oficina matriz. La otras dos ciudades en
importancia son 3. Moscú y 7.Paris. Analice las matrices potencia de la matriz de adyacencia de
A ¿que indican?

𝐴2 = 𝐴3 =
 APLICACIÓN: COLOREADO DE MAPAS

Si en el mapa de la comunidad andaluza, por ejemplo, ponemos un vértice por cada provincia y
una arista entre dos provincias si éstas son limítrofes, nos quedará el siguiente grafo.

6
5 ¿Por qué y para qué la Teoría de
1 Grafos se ha dedicado y se dedica a
2 colorear grafos con el mínimo número
7 8 de colores posibles?
4
3

Colorear ese grafo consiste en asignar colores a los vértices (puntos) de forma que no haya
vértices unidos con el mismo color.
APLICACIÓN: COLOREADO DE MAPAS

6
5
1
3
7 8

4 0 1 1 0 0 0 0 0
1 0 1 1 0 0 0 0
2
1 1 0 1 1 0 0 0
0 1 1 0 1 0 1 0
0 0 1 1 0 1 1 0
0 0 0 0 1 0 1 0
0 0 0 1 1 1 0 1
0 0 0 0 0 0 1 0
APLICACIÓN: COLOREADO DE MAPAS

Hallamos el espectro de A:

3,393
1− ≤ 𝜒 𝐺 ≤ 1 + 3,393
−2
2,6965 ≤ 𝜒 𝐺 ≤ 4,393
𝜒 𝐺 =3𝑜4
SOLUCION DEL PROBLEMA APLICATIVO
 CASO APLICATIVO
Usando este teorema, encuentre cotas sobre el número cromático para el grafo de Petersen.
Verifique el resultado volviendo a dibujar las graficas y pintando los vértices con los colores
adecuados.
 EVALUACIÓN

Forman equipos de trabajos para medir el logro de la sesión de clase, cuyos ítems
serán tomados de la hoja de trabajo y/o diapositivas.
REFERENCIAS BIBLIOGRÁFICAS

# CÓDIGO UPN CITA

Orozco Mayren, Gilberto. (2007), Geometría Analítica: Teoría y

1 516.3 OROZ
Aplicaciones. Editorial Trillas.

2 516.182 ESPI/E Espinoza, Ramos Eduardo (2004). Geometría Vectorial en R3