Una matrice

Messaggioda axpgn » 05/12/2019, 00:11

Sia data una matrice $n xx n$ il cui elemento alla riga $i$-esima e alla colonna $j$-esima è pari a $i+j-1$

Qual è il più piccolo prodotto di $n$ numeri presi da questa matrice, uno per ogni riga e per ogni colonna?



Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14555 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Una matrice

Messaggioda marmi » 07/12/2019, 20:32

Io direi
Testo nascosto, fai click qui per vederlo
(2n-1)!!

Ciao,
Andrea
marmi
Junior Member
Junior Member
 
Messaggio: 102 di 192
Iscritto il: 21/03/2008, 09:48

Re: Una matrice

Messaggioda axpgn » 07/12/2019, 23:03

Perché?
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14569 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Una matrice

Messaggioda Mathita » 07/12/2019, 23:56

Rispondere ai tuoi problemi, axpgn, mi mette molto a disagio: ho sempre paura di malinterpretare il testo o, ancora peggio, di sottovalutare il quesito.

Testo nascosto, fai click qui per vederlo
Dovrebbe essere pari al prodotto degli elementi sulla diagonale principale della matrice. \[\prod_{i=1}^{n}a_{ii}=\prod_{i=1}^{n}(2i-1)=(2n-1)!!\] L'obiettivo è minimizzare il prodotto di $n$ elementi della matrice $(a_{ij})_{i,j=1,...,n}$ con $a_{i,j}=i+j-1$ e per farlo è sufficiente minimizzare i fattori.

Dal momento che $a_{ij}$ è minimo se $i,j$ sono i valori più piccoli che abbiamo a disposizione, ragiono così: il più piccolo fattore estraibile dalla matrice è $a_{11}=1$, dopodiché considero la sottomatrice $(a_{ij})_{i,j=2,...,n}$ e ne considero il più piccolo, ossia $a_{22}=3$, al passo $k<n$ considero la sottomatrice $(a_{ij})_{i,j=\{k,...,n\}}$ da cui estraggo $a_{kk}=2k-1$ e così via fino a $n$. Funziona?
Mathita
Average Member
Average Member
 
Messaggio: 267 di 865
Iscritto il: 28/11/2015, 22:04

Re: Una matrice

Messaggioda axpgn » 08/12/2019, 00:56

Mathita ha scritto:Rispondere ai tuoi problemi, axpgn, mi mette molto a disagio: …

:shock: Addirittura?

Testo nascosto, fai click qui per vederlo
Il risultato è quello, ok :D mentre per quanto riguarda la dimostrazione ho qualche dubbio ... :-k Apparentemente mi pare una soluzione logica, che funziona però ...
Per esempio quando dici che
Mathita ha scritto:… e per farlo è sufficiente minimizzare i fattori. …
non è del tutto esatto, i fattori devono sottostare anche alla condizione "uno per riga e uno per colonna" …
Oppure quando dici che il minimo è $1$ e poi $3$ ecc. , è sensato ma non dimostrato.
Lo stesso quando passi a sottomatrici sempre più piccole: anche questo è sensato ma come puoi escludere che partendo da un valore della prima riga iniziale diverso, il prodotto finale sia minore?
Voglio dire, è vero che il minimo della prima riga è $1$ ma poi giungi a $2n-1$ ma, per esempio, se partissi da $n$ nella prima riga potresti avere $n$ anche nell'ultima (l'altra diagonale) e in tal caso quale sarebbe il prodotto minore?
In conclusione, il tuo metodo potrebbe anche essere corretto ma, a mio parere, andrebbe dimostrato in modo più formale … IMHO … :D

Mi pare chiaro che ho in mente una soluzione differente :D


Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14570 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Una matrice

Messaggioda axpgn » 08/12/2019, 01:36

@Mathita
Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.
Mathita ha scritto:… ho sempre paura di malinterpretare il testo o, ancora peggio, di sottovalutare il quesito. …

Son cose molto diverse però … nel primo caso mi fai pensare che non sono mai chiaro :? mentre nel secondo che sono stato bravo :-D


Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14571 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Una matrice

Messaggioda marmi » 08/12/2019, 11:48

Ciao.
L'idea iniziale e la -spero giusta- dimostrazione.
Testo nascosto, fai click qui per vederlo
Per $a,b,c>0$ , vale:
$(a+b)(a+c) > a(a+b+c)$

Ogni "variazione elementare" in cui sposto solo 2 elementi, rispetto alla diagonale principale,
aumenta il prodotto, per via della disuguaglianza precedente, in cui $b=c$.
Questa sorta di minimo locale ( in tante direzioni), mi fa immaginare che questo sia anche un minimo globale.

La somma delle colonne degli n numeri è uguale alla somma delle righe degli n numeri.
Se nella n-plua esiste un numero in posizione $x_1<y_1=x_0$ ( fuori dalla diagonale principale) esiste un punto $(x_2,x_1)$,
e se $x_2<x_1$ esiste $(x_3,x_2)$,...
Nella sequenza $(x_{j+1}, x_j)$ deve esistere $j$ per cui
$x_j< x_{j-1}$ e $x_{j+1}>x_j$ (non possono essere le colonne sempre in posizione minore delle righe).
Lo scambio $(x_j,x_{j-1})->(x_j,x_j)$; $(x_{j+1},x_j)->(x_{j+1},x_{j-1})$ riduce il prodotto
per la disuguaglianza iniziale.
Quindi un elemento fuori diagonale principale non puo' essere nella soluzione minima

Ciao,
Andrea
marmi
Junior Member
Junior Member
 
Messaggio: 103 di 192
Iscritto il: 21/03/2008, 09:48

Re: Una matrice

Messaggioda axpgn » 08/12/2019, 15:31

L'idea è sostanzialmente giusta ma non mi è chiara la dimostrazione … :-k

Testo nascosto, fai click qui per vederlo
Perché quella disuguaglianza fa "aumentare il prodotto"? Voglio dire, quella è la tesi mentre invece la prendi per vera come ipotesi … il resto non mi è chiarissimo … IMHO …


Questa è la mia …

Testo nascosto, fai click qui per vederlo
Definiamo le coordinate di un numero come $(i,i')$.
Supponiamo che i numeri del prodotto minimo non siano tutti sulla diagonale principale cioè non è $i=i'$ per tutti i numeri del prodotto. $(**)$
In tal caso per ogni numero in cui si abbia $i!=i'$ ne esiste almeno un altro per cui si ha $j!=j'$.
Questo perché se ce ne fosse solo uno "fuori" dalla diagonale, per la condizione posta inizialmente allora avremmo che $i'=j'$ per qualche $j'$ e ciò, appunto, non è possibile per ipotesi.
Quindi nel caso $(**)$ avremmo i due numeri $(i,i')$ e $(j,j')$ tali che $i<j$ e $i'>j'$ (o viceversa ma è la stessa cosa).
Prendiamo allora i due numeri nelle posizioni $(i,j')$ e $(j,i')$ al posto dei due precedenti e manteniamo gli altri fattori del prodotto.
Allora si ha $(i+j'-1)(j+i'-1)-(i+i'-1)(j+j'-1)=(j-i)(j'-i')<0$
Ovvero il nuovo prodotto è minore di quello precedente e questo significa che ogni volta che prendo due numeri "fuori" dalla diagonale principale posso sempre trovarne altri due che mi danno un prodotto minore.
In conclusione, il minimo prodotto si ha quando i fattori si trovano tutti sulla diagonale principale.


Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14572 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Una matrice

Messaggioda marmi » 08/12/2019, 17:52

Ciao,
immagino il punto oscuro sia questo:
Testo nascosto, fai click qui per vederlo
$(x_j,x_{j-1})->(x_j,x_j)$; $(x_{j+1},x_j)->(x_{j+1},x_{j-1})$
comporta una riduzione del prodotto,
infatti posto
$a=2x_j-1$,
$ b=x_{j+1}+x_j-1 -a = x_{j+1} -x_j$,
$c=x_{j-1}+x_j-1 -a =x_{j-1} -x_j$,

si ha:
$x_j+x_{j+1}-1=b+a$
$x_j+x_{j-1}-1=c+a$
$x_{j+1}+x_{j-1}-1=a+b+c$

e quindi si ha
$(x_j+x_j-1)(x_{j+1}+x_{j-1}-1)<(x_j+x_{j-1}-1)(x_{j+1}+x_j-1)$
essendo
$a(a+b+c) < (a+b)(a+c)$

@Alex, la differenza rispetto alla tua, mi pare che stia nel fatto che uno dei nuovi punti, nel mio caso, finisce sulla
diagonale principale. Per il resto mi paiono non molto dissimili.

Ciao,
Andrea
marmi
Junior Member
Junior Member
 
Messaggio: 104 di 192
Iscritto il: 21/03/2008, 09:48

Re: Una matrice

Messaggioda axpgn » 08/12/2019, 20:37

Essenzialmente sì.

Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14573 di 40640
Iscritto il: 20/11/2013, 22:03

Prossimo

Torna a Scervelliamoci un po'

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite