Problemi di Algebra Lineare

Oltre la matematica elementare: teoria, esercizi, e riflessioni sulle varie branche della matematica che si fanno all'università.

Re: Problemi di Algebra Lineare

Messaggioda enigma » 13/03/2015, 11:40

Gizeta ha scritto:Mi spiace dirlo, ma la soluzione ufficiale è esattamente quella di Hyka.

Per la serie: gente che scrive gare strafatta di crack?! Ma dove sta la soluzione ufficiale, e da che problem set è preso?
Avatar utente
enigma
 
Messaggi: 124
Iscritto il: 19/03/2013, 20:11

Re: Problemi di Algebra Lineare

Messaggioda Gizeta » 13/03/2015, 12:45

Il problema è Putnam 1991 A2.
Incollo sotto la soluzione ufficiale perché non mi ricordo proprio dove ho preso il file (e nel sito di Kedlaya mancano quelle degli anni inferiori al 1995).

A me pare sia loro intenzione concludere che [tex]\boldsymbol{A}-\boldsymbol{B} \not = \boldsymbol{0} \Rightarrow \boldsymbol{A}^2+\boldsymbol{B}^2=\boldsymbol{0}[/tex], altrimenti la soluzione non sarebbe tale in quanto mancherebbe la parte finale (e questo sarebbe decisamente meglio).
Non hai i permessi necessari per visualizzare i file allegati in questo messaggio.
Ultima modifica di Gizeta il 13/03/2015, 17:05, modificato 1 volta in totale.
Gizeta
 
Messaggi: 821
Iscritto il: 27/11/2013, 17:16

Re: Problemi di Algebra Lineare

Messaggioda hyka » 13/03/2015, 12:46

Se $AB = 0$ e le matrici $A$ e $B$ non sono nulle allora sono entrambe singolari.

@enigma, ovviamente facendo i conti torna, quello che chiedevo è se hai usato qualche metodo generale per scomporre un tipo particolare di matrice nel prodotto di due matrici triangolari o se è solo per questa particolare matrice.
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Problemi di Algebra Lineare

Messaggioda enigma » 13/03/2015, 13:30

hyka ha scritto:Se $AB = 0$ e le matrici $A$ e $B$ non sono nulle allora sono entrambe singolari.

Questa è in effetti l'osservazione che mancava (visto che sul momento non ci avevo pensato, la classificherei come non del tutto evidente).
La fattorizzazione che ho scritto è parte di una teoria più generale sulla decomposizione di matrici come prodotto di matrici di forma "semplice": quella in particolare è una fattorizzazione LU, e per trovarla c'è in generale un algoritmo; sul perché per quella matrice in particolare venga una forma così semplice boh, è abbastanza per caso, o forse è così che è stato inventato il problema.
Avatar utente
enigma
 
Messaggi: 124
Iscritto il: 19/03/2013, 20:11

Re: Problemi di Algebra Lineare

Messaggioda Gizeta » 13/03/2015, 14:00

Va bene, non sapevo fosse un fatto noto (qualcosa da dar per scontato, intendo).

Dimostro che [tex]\boldsymbol{A} \in \mathfrak{M}_n(\mathbb{R})[/tex] è singolare: [tex]\mathfrak{M}_n(\mathbb{R}) \ni \boldsymbol{B} \not = \boldsymbol{0}[/tex] allora esiste un vettore [tex]\boldsymbol{v} \in \mathfrak{M}(n,1,\mathbb{R})[/tex] tale che [tex]\boldsymbol{Bv} \not = \boldsymbol{0}[/tex], ma [tex]\boldsymbol{(AB)v}=\boldsymbol{A(Bv)}= \boldsymbol{0}[/tex], posto [tex]\boldsymbol{w}=\boldsymbol{Bv} \in \mathfrak{M}(n,1,\mathbb{R})[/tex] si ha

[tex]\boldsymbol{Aw}=\boldsymbol{0}[/tex]

[tex]\boldsymbol{w} \not = 0[/tex] allora [tex]rank(A)[/tex] non è massimo e conseguentemente [tex]det(\boldsymbol{A})=0[/tex].



Se per assurdo [tex]\boldsymbol{B}[/tex] fosse invertibile allora [tex]\boldsymbol{A}= \boldsymbol{AI}=\boldsymbol{A(BB^{-1})}=\boldsymbol{(AB)B^{-1}}= \boldsymbol{0B^{-1}}=\boldsymbol{0}[/tex], contro le ipotesi, quindi [tex]B[/tex] è non invertibile e [tex]det(B)=0[/tex]


[tex]\blacksquare[/tex]


Ho utilizzato due modi differenti perché vorrei che questo topic risultasse istruttivo e potesse essere d'aiuto a chi vuole provare qualche problema olimpico di matematica non elementare.
Gizeta
 
Messaggi: 821
Iscritto il: 27/11/2013, 17:16

Re: Problemi di Algebra Lineare

Messaggioda hyka » 13/03/2015, 17:56

Bella la seconda dimostrazione.

Un altro metodo(equivalente al tuo) consiste nel considerare le trasformazioni lineari associate, ricordando che una matrice è invertibile se e solo se la freccia associata è un isomorfismo.

Si ha dunque

$$V_1 \xrightarrow{f} V_2 \xrightarrow{g} V_3$$

con $gf = 0$, da cui $\operatorname{im} gf = \{0_{V_3}\}$, inoltre $\operatorname{im} f \neq \{0_{V_2}\}$ e $\operatorname{im} g \neq \{0_{V_3}\}$.

Gli isomorfismi mandano spazi di dimensione $n$ in spazi della stessa dimensione, perciò se $f$ fosse un isomorfismo si avrebbe $\operatorname{im} gf = \operatorname{im} g \neq \{0_{V_3}\}$, mentre se $g$ fosse un isomorfismo si avrebbe $\operatorname{im} gf \cong \operatorname{im} f$ cioè $\operatorname{rank} gf > 0$, assurdo.
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Problema 2

Messaggioda Gizeta » 13/03/2015, 18:52

Il bello dell'algebra lineare è che si possono girare e rigirare gli argomenti in molti modi.
Preoccupante è il fatto che io abbia trovato inizialmente la prima dimostrazione e non la seconda (palesemente più semplice) :lol:



Ecco il secondo problema (terzo col bonus):


2. Siano [tex]\boldsymbol{A,B} \in \mathfrak{M}_2(\mathbb{Z})[/tex] tali che [tex]\boldsymbol{A,A+B,A+2B,A+3B,A+4B}[/tex] siano tutte matrici invertibili le cui inverse abbiano ancora entrate in [tex]\mathbb{Z}[/tex].
Dimostrare che [tex]A+5B[/tex] è invertibile e che la sua inversa ha entrate in [tex]\mathbb{Z}[/tex].
Gizeta
 
Messaggi: 821
Iscritto il: 27/11/2013, 17:16

Re: Problemi di Algebra Lineare

Messaggioda hyka » 14/03/2015, 12:06

Soluzione brutalmente bovina.

Una matrice $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$ a entrate in $\mathbb{Z}$ è invertibile e la sua inversa ha entrate in $\mathbb{Z}$ se e solo se ha determinante $\pm 1$:
  • Se ha determinante $\pm 1$ chiaramente è invertibile e la sua inversa ha entrate in $\mathbb{Z}$.
  • Se l' inversa ha entrate in $\mathbb{Z}$ e $n > 1$ divide il determinante della matrice allora dovrà dividere tutte le entrate della matrice, quindi il quadrato di $n$ dividerà il determinante e così via all'infinito, quindi il determinante deve essere necessariamente $\pm 1$.

Ora, siano
$$A = \begin{pmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{pmatrix}$$
$$B = \begin{pmatrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{pmatrix}$$
$$\det A = a_{11} a_{22} - a_{12} a_{21}$$
$$\det B = b_{11} b_{22} - b_{12} b_{21}$$
$$T = a_{11} b_{22} + a_{22} b_{11} - a_{12} b_{21} - a_{21} b_{12}$$

le ipotesi del problema equivalgono a

$$\begin{cases} \det A = a \\ \det A + \det B + T = b \\ \det A + 4 \det B + 2 T = c \\ \det A + 9 \det B + 3 T = d \\ \det A + 16 \det B + 4 T = e\end{cases}$$

con $a, b, c, d, e \in \{\pm 1\}$. Passando alla matrice completa

$$\left( \begin{array}{ccc|c}
1 & 0 & 0 & a \\
1 & 1 & 1 & b \\
1 & 4 & 2 & c \\
1 & 9 & 3 & d \\
1 & 16 & 4 & e
\end{array} \right)
\Longrightarrow
\left( \begin{array}{ccc|c}
1 & 0 & 0 & a \\
0 & 1 & 1 & b - a \\
0 & 0 & -2 & 3a - 4b + c \\
0 & 0 & -6 & 8a - 9b + d \\
0 & 0 & -12 & 15 a - 16b + e
\end{array} \right)$$

affinché il sistema sia compatibile si deve avere

$$\begin{cases}18 a - 24 b + 6c = 16a - 18b + 2d \\ 16a - 18b + 2d = 15a - 16b + e \end{cases}$$

cioè

$$\begin{cases} a - d = 3(b - c) \\ a + 2d = 2b + e\end{cases}$$

Ricordando che $a, b, c, d \in \{\pm 1\}$ si ottiene $a = d$ e $b = c$ dalla prima equazione, $a = b = e$ dalla seconda, perciò dal sistema originale si ottiene $T = 0$, $\det B = 0$, $\det A = a$ e quindi $\det A + n^2 \det B + nT = a \in \{\pm 1\}$ cioè $A + nB$($n \in \mathbb{Z}$) è una matrice invertibile la cui inversa ha entrate in $\mathbb{Z}$.

Saranno stati commessi orrori? :?
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Problemi di Algebra Lineare

Messaggioda Gizeta » 14/03/2015, 13:49

hyka ha scritto:Una matrice $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$ a entrate in $\mathbb{Z}$ è invertibile e la sua inversa ha entrate in $\mathbb{Z}$ se e solo se ha determinante $\pm 1$ [...]


Bene, per dimostrarlo è sufficiente applicare Binet e il secondo teorema di Laplace:

[tex]\displaystyle 1=det(I)=det(A^{-1}A)=det(A^{-1})det(A) \rightarrow det(A^{-1})=\frac{1}{det(A)}[/tex]

[tex]det(A^{-1}) \in \mathbb{Z} \Rightarrow det(A)= \pm 1[/tex]

Viceversa se [tex]det(A)=\pm 1[/tex] allora [tex]A[/tex] è invertibile e [tex]\displaystyle A^{-1}=\frac{Ad(A)}{det(A)}=(\pm 1)\cdot Ad(A) \in \mathfrak{M}_2(\mathbb{Z})[/tex]

[tex]\blacksquare[/tex]


Ora, siano [...]


Siano [tex]A=(A^1,A^1)[/tex] e [tex]B=(B^1,B^2)[/tex], allora

[tex]det(A+nB)=det(A^1+nB^1,A^2+nB^2) \stackrel{prop.det.}{=}det(A^1,A^2)+ndet(A^1,B^2)+n det(B^1,A^2)+n^2 det(B^1,B^2)=det(A)+n^2det(B)+nT[/tex]

ove [tex]T=det(A^1,B^2)+det(B^1,A^2)[/tex]

Immagino sia questo il ragionamento.




Il resto sono conti che controllo questa sera :D



Ti lascio un suggerimento per la soluzione bella

Testo nascosto:
Sia [tex]P(n)=det(A+nB)[/tex] [...]
Gizeta
 
Messaggi: 821
Iscritto il: 27/11/2013, 17:16

Re: Problemi di Algebra Lineare

Messaggioda hyka » 14/03/2015, 15:34

Gizeta ha scritto:Ti lascio un suggerimento per la soluzione bella

Testo nascosto:
Sia [tex]P(n)=det(A+nB)[/tex] [...]


$P(n) = (\det B) n^2 + \det A + T$ non può essere una parabola perché le ipotesi insieme al principio dei cassetti ci dicono che dovrebbe assumere lo stesso valore in almeno tre punti(cosa impossibile per una parabola) quindi è costante e $\det(A + nB) = \det A \in \{\pm 1\}$?
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

PrecedenteProssimo

Torna a Matematica Universitaria

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti