A totalmente unimodulare => [A I] unimodulare
Salve a tutti,
mi è chiara la dimostrazione di:
[A I] unimodulare => A totalmente unimodulare
ma non mi è chiaro invece come dimostrare:
A totalmente unimodulare => [A I] unimodulare
Vi ringrazio anticipatamente.
mi è chiara la dimostrazione di:
[A I] unimodulare => A totalmente unimodulare
ma non mi è chiaro invece come dimostrare:
A totalmente unimodulare => [A I] unimodulare
Vi ringrazio anticipatamente.
Risposte
Nessuno? 
Il teorema da dimostrare sarebbe il seguente:
Data una matrice $A (m \times n)$, $A$ è totalmente unimodulare se e solo se $[A \quad I_m]$ è unimodulare. Dove $I_m$ è la matrice identità $(m \times m)$ e dove con $[A \quad I_m]$ si intende la matrice formata dalle colonne di $A$ e quelle di $I_m$.
A me interessa solo la dimostrazione del "solo se".
Ho cercato un po' in rete, ma in tutte le dimostrazioni del teorema che ho trovato c'è semplicemente scritto che il "solo se" è banale e quindi non viene fornita una dimostrazione.
Il teorema da dimostrare sarebbe il seguente:
Data una matrice $A (m \times n)$, $A$ è totalmente unimodulare se e solo se $[A \quad I_m]$ è unimodulare. Dove $I_m$ è la matrice identità $(m \times m)$ e dove con $[A \quad I_m]$ si intende la matrice formata dalle colonne di $A$ e quelle di $I_m$.
A me interessa solo la dimostrazione del "solo se".
Ho cercato un po' in rete, ma in tutte le dimostrazioni del teorema che ho trovato c'è semplicemente scritto che il "solo se" è banale e quindi non viene fornita una dimostrazione.
ciao,
cosa intendi con questa notazione:$[A\ I_m]$ è un prodotto tra matrici, un semplice accostamento,...
cosa intendi con questa notazione:$[A\ I_m]$ è un prodotto tra matrici, un semplice accostamento,...
"hamming_burst":
ciao,
cosa intendi con questa notazione:$[A\ I_m]$ è un prodotto tra matrici, un semplice accostamento,...
Ciao
$[A\ I_m]$ è la matrice formata dalle colonne di $A$ e le colonne di $I_m$.
Se indichiamo le colonne di A come $\pi_1, ..., \pi_n$ e le colonne di $I_m$ come $e_1, ..., e_m$ allora:
$[A\ I_m] = (\pi_1\ ...\ \pi_n\ e_1\ ...\ e_m)$
Ok ragazzi ci ho pensato un po' e forse ho trovato una possibile dimostrazione.
Vi prego ditemi se vi convince e se ho sbagliato qualche passaggio.
Dunque, vogliamo dimostrare:
se $A_{(m \times n)}$ è totalmente unimodulare allora $[A\ I_m]$ è unimodulare.
Per dimostrare che $[A\ I_m]$ è unimodulare, basta mostrare che ogni sua sottomatrice $m \times m$ ha determinate 1, 0 o -1.
Consideriamo quindi la generica sottomatrice $B_{(m \times \m)}$ di $[A\ I_m]$.
Essa sarà formata da $m$ colonne di cui alcune di $A$ e altre di $I_m$.
Indichiamo con $\pi_{j_1},\ ...,\ pi_{j_r}$ le colonne selezionate da $A$ e con $e_{j_{r+1}},\ ...,\ e_{j_m}$ le colonne selezionate da $I_m$, con $0 \le r le m$.
Allora:
$B = (\pi_{j_1}\ ...\ pi_{j_r}\ e_{j_{r+1}}\ ...\ e_{j_m})$
Poiché ogni colonna $e_j$ è formata da tutti 0 e un 1 in $j$-esima posizione, essendo $B_1$ la sottomatrice ottenuta da $B$ rimuovendo la colonna $e_j$ e la $j$-esima riga, possiamo dire che:
$|det(B)| = |det(B_1)|$
Iterando il raggionamento: sia $B_k$ (con $k = m-r$) la sottomatrice ottenuta da $B$ rimuovendo ogni colonna $e_j$ e la corrispondente $j$-esima riga, possiamo dire che:
$|det(B)| = |det(B_k)|$
Poiché $B_k$ è una sottomatrice di $A$ ed inoltre $A$ è totalmente unimodulare, possiamo dire che:
$|det(B_k)| \in \{ 0, 1 \}$
e dunque:
$|det(B)| \in \{ 0, 1 \}$
da cui per definizione segue la tesi.
Vi prego ditemi se ho sbagliato qualche ragionamento, grazie!
Vi prego ditemi se vi convince e se ho sbagliato qualche passaggio.
Dunque, vogliamo dimostrare:
se $A_{(m \times n)}$ è totalmente unimodulare allora $[A\ I_m]$ è unimodulare.
Per dimostrare che $[A\ I_m]$ è unimodulare, basta mostrare che ogni sua sottomatrice $m \times m$ ha determinate 1, 0 o -1.
Consideriamo quindi la generica sottomatrice $B_{(m \times \m)}$ di $[A\ I_m]$.
Essa sarà formata da $m$ colonne di cui alcune di $A$ e altre di $I_m$.
Indichiamo con $\pi_{j_1},\ ...,\ pi_{j_r}$ le colonne selezionate da $A$ e con $e_{j_{r+1}},\ ...,\ e_{j_m}$ le colonne selezionate da $I_m$, con $0 \le r le m$.
Allora:
$B = (\pi_{j_1}\ ...\ pi_{j_r}\ e_{j_{r+1}}\ ...\ e_{j_m})$
Poiché ogni colonna $e_j$ è formata da tutti 0 e un 1 in $j$-esima posizione, essendo $B_1$ la sottomatrice ottenuta da $B$ rimuovendo la colonna $e_j$ e la $j$-esima riga, possiamo dire che:
$|det(B)| = |det(B_1)|$
Iterando il raggionamento: sia $B_k$ (con $k = m-r$) la sottomatrice ottenuta da $B$ rimuovendo ogni colonna $e_j$ e la corrispondente $j$-esima riga, possiamo dire che:
$|det(B)| = |det(B_k)|$
Poiché $B_k$ è una sottomatrice di $A$ ed inoltre $A$ è totalmente unimodulare, possiamo dire che:
$|det(B_k)| \in \{ 0, 1 \}$
e dunque:
$|det(B)| \in \{ 0, 1 \}$
da cui per definizione segue la tesi.
Vi prego ditemi se ho sbagliato qualche ragionamento, grazie!
utilizzare la definizione di sottomatrice mi pare sia una strada corretta.
la parola "selezione" lo intendi legato al calcolo del determinante con la classica formulazione, oppure per la semplicemente creazione di una sottomatrice?
comunque per me la strada che hai seguito è corretta, per i passaggi aspetto la risposta sopra
"pnp":
Indichiamo con $\pi_{j_1},\ ...,\ pi_{j_r}$ le colonne selezionate da $A$ e con $e_{j_{r+1}},\ ...,\ e_{j_m}$ le colonne selezionate da $I_m$, con $0 \le r le m$.
la parola "selezione" lo intendi legato al calcolo del determinante con la classica formulazione, oppure per la semplicemente creazione di una sottomatrice?
comunque per me la strada che hai seguito è corretta, per i passaggi aspetto la risposta sopra
"hamming_burst":
utilizzare la definizione di sottomatrice mi pare sia una strada corretta.
la parola "selezione" lo intendi legato al calcolo del determinante con la classica formulazione, oppure per la semplicemente creazione di una sottomatrice?
Intendo per la semplice creazione di una sottomatrice.
cioè nel senso, data la matrice $[A\ I_m]$ che è $(m \times n)$ una sua qualsiasi sottomatrice $(m \times m)$ può essere ottenuta prendendo $r$ colonne da A e $m - r$ colonne da $I_m$, con $0 \le r \le m$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo