Per la serie: gente che scrive gare strafatta di crack?! Ma dove sta la soluzione ufficiale, e da che problem set è preso?Gizeta ha scritto:Mi spiace dirlo, ma la soluzione ufficiale è esattamente quella di Hyka.
Problemi di Algebra Lineare
Re: Problemi di Algebra Lineare
Re: Problemi di Algebra Lineare
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).
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.
Re: Problemi di Algebra Lineare
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.
@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.
Re: Problemi di Algebra Lineare
Questa è in effetti l'osservazione che mancava (visto che sul momento non ci avevo pensato, la classificherei come non del tutto evidente).hyka ha scritto:Se $AB = 0$ e le matrici $A$ e $B$ non sono nulle allora sono entrambe singolari.
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.
Re: Problemi di Algebra Lineare
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.
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.
Re: Problemi di Algebra Lineare
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.
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.
Problema 2
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)
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].
Preoccupante è il fatto che io abbia trovato inizialmente la prima dimostrazione e non la seconda (palesemente più semplice)
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].
Re: Problemi di Algebra Lineare
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$:
$$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?
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$.
$$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?
Re: Problemi di Algebra Lineare
Bene, per dimostrarlo è sufficiente applicare Binet e il secondo teorema di Laplace: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$ [...]
[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]
Siano [tex]A=(A^1,A^1)[/tex] e [tex]B=(B^1,B^2)[/tex], alloraOra, siano [...]
[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
Ti lascio un suggerimento per la soluzione bella
Testo nascosto:
Re: Problemi di Algebra Lineare
$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\}$?Gizeta ha scritto: Ti lascio un suggerimento per la soluzione bella
Testo nascosto: