MAD: Máximo común divisor

Comenzamos explicando El algoritmo de la división, que intenta dar consistencia al procedimiento habitual de división entre números enteros, recordando que esta no existe como tal, ya que la división no siempre existe. Sin embargo podemos dar un resultado que nos ayuda a comprender que entendemos por división en los números enteros.

Teorema: Dados dos números enteros $a$ y $b$, con $a$ no nulo, la división euclídea asocia un cociente $q\in\mathbb{Z}$ y un resto $r\in\mathbb{Z}$, únicos, que verifican: $$b=q\,a+r,\quad 0\leq r<|a|$$

El siguiente tema tratado en le máximo común divisor:

Consideremos dos números enteros Si $a$ y $b$ distintos de cero, decimos que $c$ es un divisor común de $a$ y $b$ si $c|a$ y $c|b$. Cuando existen, únicamente, como divisores comunes 1 y -1 de los números $a$ y $b$ , estos se llaman coprimos o números primos entre sí.

Un número entero $d$ se llama máximo común divisor de los números $a$ y $b$, $d=mcd(a,b)$, cuando:

  1. d es divisor común de los números $a$ y $b$ y
  2. $c$ es divisor de $a$ y $b$, entonces $c|d$.

En la próxima sesión veremos el algoritmo de Euclides como método para calcular el mcd().

 

Ejercicio: Probar que el cuadrado de todo número entero impar puede escribirse de la forma $4k+1$ para algún entero $k$.
Posted in: Matemática Discreta by admin No Comments

MAD: Divisibilidad

El concepto de divisibilidad es uno de los más importantes que veremos en Teoría de números. Con él pretendemos dar una sustitución de la división que no siempre es posible en el conjunto de los números enteros.

Decimos que un número entero $b$ es divisible entre un entero $a$ (distinto de cero) si existe un entero $c$ tal que: $$b = a · c.$$
Se suele expresar de la forma $a|b$, que se lee: $a$ divide a $b$, o $a$ es un divisor de $b$, o, también $b$ es múltiplo de $a$.

Utilizando esta definición hemos probado propiedades de la divisibilidad como

  • $1|a$ y $a|0$ para todo $x\in\mathbb{Z}$.
  • Si $a|b$, entonces $|a|<|b|$.
  • Si $a|b$ y $b|a$, entonces $a=\pm b$.
  • Si $a|b$, entonces $a|(bx)$ para todo $x\in\mathbb{Z}$.
  • Si $a|b$ y $b|c$, entonces $a|c$.

 

Ejercicio: Probar que si $a|b$ y $a|c$, entonces $a|(bx+cy)$, para todo $x,y\in\mathbb{Z}$
Posted in: Matemática Discreta by admin No Comments

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