Matematica Discreta
Compito (12 crediti) 23 Maggio 2013
Nome e Cognome:
Numero Matricola:
Giustificare ogni risposta.
Esercizio 1
Sia X un insieme. Si dimostri che per tutti i sottinsiemi A, B, C di X vale la seguente relazione:
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Soluzione: Si veda Example 2.5 negli appunti del corso.
Esercizio 2
Si determini qual e’ il resto della divisione di (81)99per 7.
Soluzione: 7 e’ un numero primo. Quindi il teorema di Fermat ci permette di dire che 816 ≡ 1 (mod 7). Allora abbiamo:
8199= 81(6×16)+3= (816)16× (81)3≡ 116× (34)3= 312= (36)2≡ 12= 1 (mod 7).
Se non vogliamo applicare il Teorema di Fermat, calcoliamo nel modo seguente:
8199= (34)99= (32× 32)99≡ (2 × 2)99= 499= 2198= (23)66= 866≡ 166= 1 (mod 7).
Esercizio 3
Si provi per induzione che
2n− 1 = X
0≤k≤n−1
2k.
Soluzione: Caso base: n = 1. 21− 1 = 1 = 20=P
0≤k≤02k. Supponiamo vera l’uguaglianza per n, cioe’
2n− 1 = X
0≤k≤n−1
2k,
e dimostriamola per n + 1:
X
0≤k≤(n+1)−1
2k = X
0≤k≤n
2k= ( X
0≤k≤n−1
2k) + 2n=Ip.Ind.(2n− 1) + 2n = 2n+1− 1.
Esercizio 4
(a) Si trovi l’insieme S delle soluzioni del seguente sistema di equazioni lineari omogenee a coefficienti nel campo Q dei numeri razionali:
x1+ x2+ x3+ x4 = 0 2x1+ 3x2+ 2x3+ x4 = 0 3x1+ 4x2+ 3x3+ 2x4 = 0
(b) Come si e’ visto a lezione S e’ un sottospazio di Q4 . Se ne calcoli la dimensione.
Soluzione: Si veda la soluzione del recupero del II compitino.
Esercizio 5
Provare che, se una matrice quadrata M e’ diagonalizzabile e invertibile, allora anche la matrice inversa M−1 e’
diagonalizzabile. Se a1, . . . , an sono gli autovalori distinti di M , (a) si provi che ai6= 0 per ogni i.
(b) si calcolino gli autovalori di M−1. Soluzione:
Se M `e invertibile, allora esiste una matrice M−1tale che M M−1`e la matrice identica. Se M `e diagonalizzabile esiste una matrice invertibile P tale che P−1M P `e una matrice diagonale e sulla diagonale compaiono gli autovalori di M . (a) Abbiamo che 0 6= det(M ) = det(P−1M P ). Poich´e il determinante della matrice diagonale P−1M P `e il prodotto degli elementi della sua diagonale principale, ossia gli autovalori di M , allora gli autovalori di M devono essere necessariamente diversi da 0.
(b) Detta I la matrice identica, si ha
I = P−1P = P−1IP = P−1M M−1P = P−1M IM−1P = P−1M P P−1M−1P = (P−1M P )(P−1M−1P ).
Dunque P−1M−1P `e la matrice inversa di P−1M P , e quest’ultima `e diagonale. Ma l’inversa di una matrice diagonale
`e diagonale, dunque P−1M−1P `e diagonale, cio`e M−1`e diagonalizzabile. Inoltre l’elemento di posto ii dell’inversa di una matrice diagonale `e l’inverso dell’elemento di posto ii della matrice diagonale data. Ci`o implica che gli autovalori di M−1 sono esattamente gli inversi degli autovalori di M .
