MAD: Inducción matemática

Antes de meternos de lleno en la teoría de números trataremos el tema de la Inducción matemática, una herramienta tremendamente útil para ciertos ejercicios que veremos,

La inducción matemática ayuda a demostrar una proposición determinada mediante el esquema del razonamiento siguiente. Llamemos $P_n$ a la proposición, donde $n$ es el rango.

  • Se demuestra que $P_0$, el primer valor que cumple la proposición (iniciación de la inducción), es cierta.
  • Se demuestra que si se asume $P_k$ como cierta y como hipótesis inductiva, entonces $P_{k+1}$lo es también, y esto sin condición sobre el entero natural $k$ (relación de inducción).

Luego, demostrado esto, concluimos por inducción, que $P_n$ es cierto para todo natural $n$.

La inducción puede empezar por otro término que $P_0$, digamos por $P_{n_0}$. Entonces $P_n$ será válido a partir del número $n_0$, es decir, para todo natural $n \ge n_0$.

Ejercicio: Probar $6^n$ es un número que acaba en 6 para todo $n \ge 1$
Posted in: Matemática Discreta by admin No Comments

MAD: Presentación

En la presentación del día de hoy hemos visto

  • Presentación
  • Objetivos de la asignatura
  • Metodología y Evaluación
  • Bibliografía

Objetivos, Metodología y Evaluación

El contenido de la asignatura está centrado en tres bloques:

  • Teoría de números
  • Teoría de grafos
  • Combinatoria y Lógica

En la guía se detallan en la guía de Grado podéis encontrar la metodología y la evaluación.

Bibliográfica

Básica

  • García Merayo F., Matemática Discreta. Ed. Paraninfo, 2015
  • García Merayo F., Hernández G., Nevot A. Problemas resueltos de Matemáticas Discreta., Ed. Paraninfo, 2018
  • www.ingebook.com

Aconsejable

  • Vieites A. M., y otros. Teoría de grafos. Ejercicios y problemas resueltos. Paraninfo, 2014.
  • Lipschutz S., Lipson M. 2000 Problemas resueltos de matemática discreta. McGraw-Hill, 2004
  • Bujalance, E. y otros. Elementos de Matemática Discreta. Ed. Sanz y Torres, Madrid, 2005
  • Bujalance, E. y otros. Problemas de Matemática Discreta. Ed. Sanz y Torres, Madrid, 2005
  • Grimaldi, R. P. Discrete and Combinatorial Mathematics. Pearson New International Edition, 2013
Posted in: Matemática Discreta by admin No Comments

ALG: Diagonalización ortogonal

En día de hoy consideramos un caso particular de endomorfismos y matrices que se consideran son simétricos. Para ello definimos un endomorfismo simétrico.

Si consideramos un espacio eunclídeo $\mathcal{E}$, con el producto escalar $\bullet$, se dice que un endomorfismo $f:\mathcal{E}\to\mathcal{E}$ es simétrico si: $$\vec{u}\bullet f(\vec{v})=\vec{v}\bullet f(\vec{u}),\quad\forall \vec{u},\vec{v}\in\mathcal{E}.$$

La característica de un endomorfismo simétrico está asociada a su matriz, que también es simétrica. Pues bien, si tenemos un espacio vectorial finito y la matriz $A$ es la matriz de un endomormismo $f$ en una base ortonormal del espacio, entonces $f$ es simétrico si, y sólo si, $A$ es simétrica.

Este resultado tiene una implicación muy importante, pues en este caso podemos afirmar que $f$ (o más bien su matriz asociada $A\in \mathcal{M}_n(\mathbb{R})$) es diagonalizable ortogonalmente; es decir, existe $D$, matriz diagonal, y $P$ matriz ortogonal tal que $$A=P\,D\,P^{-1}.$$

Una aplicación es al caso de las cónicas. Una cónica es por definición el lugar geométrico de la ecuación:
$$ax^2+by^2+2cxy+dy+fx=e$$
que equivale a
$$[x\,\,y]\begin{bmatrix} a&c\\ b&d\end{bmatrix}\begin{bmatrix} x\\ y\end{bmatrix}+[d \,\,f]\begin{bmatrix} x\\ y\end{bmatrix}=e$$
Como la matriz $A=\begin{bmatrix} a&c\\ b&d\end{bmatrix}$ es diagonalizable, existirá $A=PDP^t$, de modo que
$$e=\vec{v}^tPDP^t\vec{v}+[d\,\, f]\vec{v}=\vec{v}^tPDP^t\vec{v}+[d\,\, f]PP^t\vec{v}$$
Si ponemos $P^t\vec{v}=\vec{u}$, la cónica quedará como:
$$e=\vec{u}^tD\vec{u}+[d\,\, f]P\vec{u}.$$
De donde podremos ver que $$e=\lambda_1 \vec{u}_1^2+\lambda_2 \vec{u}_2^2+\alpha\vec{u}_1+\beta\vec{u}_2,$$ donde $\lambda_i$ son los autovalores de $A$ y $\vec{u}_i$ van en la dirección de la base ortonormal de los autovectores de $A$.

Ejercicio: Probar que la matriz
$$\begin{bmatrix} -1 & 1&0\\ 1&-1&0\\ 0&0&-2\end{bmatrix}$$ es diagonalizable ortogonalmente.
Posted in: Álgebra Lineal by admin No Comments

ALG: Diagonalización de una matriz

El proceso de diagonalización de una matriz necesita conocer los autovalores y autovetores de la matriz. Sea, por tanto, $A$ una matriz cuadrada de orden $n$, y sean $\lambda_i$ los autovalores de dicha matriz. Entonces

La matriz $A$ es diagonalizable si, y sólo si, se cumple: $a)$ el número de soluciones de la ecuación característica es igual a $n$; $b)$ la dimensión del subespacio $\mathcal{C}_{\lambda_i}$ coincide con la multiplicidad del autovalor $\lambda_i$ como solución de la ecuación característica de $A$.

Este resultado nos permite saber si una matriz es diagonalizable, y en caso de serlo encontrar las matrices $D$ y $C$, tales que $D=C^{-1}\,A\,C$.

Si $A$ es diagonalizable, $D$ será la matriz diagonal que tendrá por elementos en su diagonal los autovalores de $A$, y $C$ será la matriz que tiene por columnas los autovectores de $A$.

 

Ejercicio: Calcula las matrices $D$ (diagonal) y $C$, que diagonaliza la matriz real $$\begin{bmatrix}
0 & 1 & -1 \\
1 & 1 & 0 \\
-1 & 0 & 1 \end{bmatrix}$$
Posted in: Álgebra Lineal by admin No Comments

ALG: Autovectores y subespacios propios

El pasado día vimos cómo calculábamos los autovalores, las soluciones de la ecuación que plantea el determinante $$p_A(\lambda)=det(A-\lambda\, I),$$

El polinomio $p_A(\lambda)$ es el polinomio característico de $A$.

Cada valor propio tiene asociado un conjunto $\mathcal{C}_\lambda=\{\vec{v}\in\mathbb{K}^n|A\vec{v}=\lambda\vec{v}\}$, que se determina resolviendo el sistema homogéneo $(A-\lambda\, I)\vec{x}=\vec{0}$. Las soluciones de estos sistemas serán los vectores propios de la matriz.

Así al número de veces que un autovalor λ se repite como raíz del polinomio característico se le llama multiplicidad algebraica y se representa por $m_a(\lambda)$. Y al número máximo de autovectores linealmente independientes que tiene asociado un autovalor λ, es decir la dimensión del subespacio propio $\mathcal{C}_\lambda$, se le llama multiplicidad geométrica de λ y se representa por $m_g(\lambda)$. Estos dos números están relacionados por una desigualdad: $$m_g(\lambda)\leqslant m_a(\lambda)$$

 

Ejercicio: Calcula los vectores propios de la matriz real $$\begin{bmatrix}
0 & 1 & -1 \\
1 & 1 & 0 \\
-1 & 0 & 1 \end{bmatrix}$$
Posted in: Álgebra Lineal by admin No Comments

EFM: Repaso

Último día de clase y lo dejamos para repasar.

EFM: Aplicación de la transformada de Laplace

La transformada de Laplace tiene una serie de propiedades que la hacen útil en el para resolver ecuaciones diferenciales y de sistemas lineales. Una de las ventajas más significativas radica en que la integración y derivación se convierten en multiplicación y división. Esto transforma las ecuaciones diferenciales e integrales en ecuaciones polinómicas, mucho más fáciles de resolver.

ALG: Autovectores y autovalores

Comenzamos explicado que son los valores y vectores propios, o autovalores y autovectores, de una matriz y.

Hemos aprendido a calcular los autovalores de una matriz cuadrada. Recordad que para nuestro propósito necesitamos encontrar las soluciones de la ecuación que plantea el determinante $$det(A-\lambda\, I),$$ siendo $A\in\mathcal{C}_n(\mathbb{K})$, donde $\mathbb{K}$ es $\mathbb{R} ó \mathbb{C}$, la matriz cuadrada y $I$ la indentidad en $\mathcal{C}_n(\mathbb{K})$.

El polinomio p(λ) = det(A – λI) es el polinomio característico de A: los valores propios de una matriz son los ceros de su polinomio característico (soluciones de la ecuación característica).

 

Ejercicio: Calcular los valores propios de la matriz real $$\begin{bmatrix}0 & 1 & -1 \\ 1 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}$$
Posted in: Álgebra Lineal by admin No Comments

ALG: Matrices ortogonales

Definimos las aplicaciones ortogonales a las aplicaciones de un espacio vectorial con producto escalar $(\mathcal{E},\bullet)$ que conservan el producto escalar; es decir, $f:\mathcal{E}\to \mathcal{E}$, es ortogonal si $$f(\vec{x})\bullet f(\vec{y})=\vec{x}\bullet \vec{y},\quad\forall\,\vec{x}, \vec{y}\in\mathcal{E}$$

Propiedades que cumple una aplicación ortogonal:

  • Es lineal
  • Conserva la norma; es decir, $||f(\vec{x})||=||\vec{x}||$
  • Dos vectores son ortogonales si, y solo si, sus imágenes son ortogonales
  • La aplicación es biyectiva
  • Los vectores propios de valores propios distintos son ortogonales
  • La imagen de una base ortonormal es ortonormal
  • Su matriz asociada es ortogonal

Hay varias formas de definir una matriz ortogonal. Nosotros emplearemos la que parte de la teoría de matrices. Así diremos que de una matriz cuadrada es ortogonal si su inversa coincide con su traspuesta; es decir,$$A^{-1}=A^t.$$

Para nosotros será muy útil el siguiente resultado:

Teorema: Una matriz $A\in\mathcal{M}_n(\mathbb{R})$ es ortogonal si y sólo si sus vectores filas o vectores columna son cada uno un conjunto ortonormal de vectores.

Otra propiedad muy útil es que el determinante de una matriz ortogonal es 1 ó -1.

La relación entre los concepto de aplicación ortogonal y matriz ortogonal es muy sencilla:

Teorema: Si tenemos un endomorfismo ortogonal sobre una base ortonormal, entonces su matriz asociada es una matriz ortogonal.

Dicho de otro modo, las aplicaciones ortogonales, aquellas que conservan el producto escalar, tienen por matrices asociadas a matrices ortogonales (matrices cuadradas que cumplen que su inversa coincide con la traspuesta). Además se cumple, que en una matriz ortogonal las filas o columnas, consideradas como vectores, son ortonormales.

 

Ejercicio: Hallar $a,b,c,\alpha,\beta,\gamma\in\mathbb{R}$ de manera que la matriz \begin{pmatrix}a & 2a & 2/3 \\ b & -b & c \\ \alpha & \beta & \gamma\end{pmatrix} sea ortogonal
Posted in: Álgebra Lineal by admin No Comments

ALG: Proyección ortogonal

El pasado día veíamos que cuando $S$ era un subespacio vectorial entonces $$E=S\oplus S^{\bot}$$

Esto implica que para todo vector $\vec{v}\in E$ existirán dos únicos vectores $\vec{u}\in S$ y $\vec{w}\in S^{\bot}$, tales que $$\vec{v}=\vec{u}+\vec{w}.$$

Estos vectores $\vec{u}$ o $\vec{w}$ son lo que llamamos proyecciones ortogonales de $\vec{v}$ sobre $S$ o $S^{\bot}$ respectivamente.

La definición clásica nos dice que si $S\subset E$, un subespacio vectorial de un espacio euclídeo, para nuestros casos finitamente generado, llamamos proyección ortogonal del vector $\vec{v}$ sobre el subespacio $S$, al único vector $\vec{u}\in S$ talque $\vec{v}-\vec{u}\in S^{\bot}$.

A la aplicación $proy_S:E\to S$ que a cada vector de $E$ le hace corresponder su proyección ortogonal sobre $S$, se le denomina del mismo modo: proyección ortogonal.

Veamos un método para calcular la proyección ortogonal. Primero empezamos con la proyección sobre un vector. Si $S=<\vec{s}>$; es decir, es una recta, entonces $$proy_\vec{s}(\vec{v})=\frac{\vec{v}\bullet\vec{s}}{\parallel\vec{s}\parallel^2}\vec{s}.$$

Extenderlo a cualquier subespacio es sencillo, solo necesitamos una base ortogonal del subespacio: Sea $\{\vec{u}_1,\vec{u}_1,\ldots,\vec{u}_m\}$ una base ortogonal de $S$, entonces
$$proy_S(\vec{v})=\sum_{i=1}^m\frac{\vec{v}\bullet\vec{u}_i}{\parallel\vec{u}_i\parallel^2}\vec{u}_i.$$
Si además la base es ortonormal la expresión se reduce mucho:
$$proy_S(\vec{v})=(\vec{v}\bullet\vec{u}_i)\vec{u}_1+(\vec{v}\bullet\vec{u}_2)\vec{u}_2+\ldots+(\vec{v}\bullet\vec{u}_m)\vec{u}_m.$$

El propósito es determinar dado un subespacio vectorial $S\subset\mathbb{R}^n$ y un vector, o punto, $\vec{v}\in\mathbb{R}^n$, minimizar la distancia de $\vec{v}$ a cualquier $\vec{s}\in S$. Para conseguirlo utilizamos el siguiente resultado:

Teorema: Sea $S\subset\mathbb{R}^n$ un sube.v., $\vec{v}\in\mathbb{R}^n$ y $\vec{s}\in S$, son equivalentes

  1. $\vec{s}\in S$ es la proyección ortogonal de $\vec{v}$ sobre $S$, $proy_S(\vec{v})$; es decir, $\vec{v}-\vec{s}\in S^{\bot}$
  2. $\vec{s}\in S$ es la mejor aproximación de $\vec{v}$ sobre $S$; es decir,$\parallel \vec{v}-\vec{s}\parallel\leq \parallel \vec{v}-\vec{w}\parallel\,\forall \vec{w}\in S$
Ejercicio: Deducir que la distancia entre un punto $P(x_0,y_0)$ y la recta $r:ax+by+c=0$ viende dada por la fórmula $$d(P,r)=\frac{ax_0+by_0+c}{\sqrt{a^2+b^2}}$$
Posted in: Álgebra Lineal by admin No Comments