Am incercat sa generalizez urmatoarea problema data in acest an la Olimpiada de Matematica a studentilor din sud-estul Europei

"Fie n un numar natural nenul si matricea A de ordinul n care are pe linia i si coloana j restul impartirii la 3 al numarului i^j+j^i. Sa se determine valoarea maxima a lui n pentru care determinantul matricei A este nenul"

Se arata ca daca n>6 atunci linia 1 coincide cu linia 7 si deci determinantul este nul. Deci n<7. Se verifica prin calcul ca pentru n=6 determinantul este nul iar pentru n=5 este nenul. Deci n=5

Generalizare :
Fie n un numar natural nenul si p un numar prim. Fie A matricea de ordinul n care are pe linia i si coloana j restul impartirii la p al numarului
i^j+j^i. Sa se determine valoarea maxima a lui n pentru care determinantul matricei A este nenul.

Am reusit sa arat ca daca n>p(p-1) atunci linia 1 concide cu linia
p(p-1)+1 si deci determinatul este nul. Deci n<p(p-1)+1
Problema este ca verificarea prin calcul a faptului daca pentru
n=p(p-1); n=p(p=1)-1 etcdeterminantele aferente sunt sau nu sunt nule nu prea mi-a mers.
Va rog sa ma ajutati cu o metoda de calcul (cu justificare...)
Se intampla cumva ca in cazul general valoare maxima a lui n sa fie
p(p-1)-1 ?

Va multumesc

Izolez problema din cele de mai sus si introduc notatie in ea, ca sa-mi fie deja usor sa-mi dau drumul. Ma leg de urmatoarea problema care este usor de rezolvat cu computerul...

[Citat] (aproximativ) Fie p un numar prim. Consideram in cele ce urmeaza mai multe matrici cu intrari in ZZ / p, inelul de intregi modulo p. Fie n natural. Consideram matricea A( n, p ) de marime nxn care are pe linia i si coloana j numarul i^j + j^i modulo p. Din cauza numarului finit de valori pe care le pot lua i,j modulo p si a numarului finit de valori pe care le pot lua puterile lor modulo eulerphi(p), avem o repetare periodica de linii/coloane, deci exista o valoare maxima a lui n pentru care determinantul matricei A( n,p ) este nenul. Notam acest maxim cu n(p). Sa se determine n(3). Sa se determine n(5). Sa se determine n(7).

Sa vedem cum stau lucrurile cu urmatoarele numere prime, de exemplu 5 si 7.
Pentru 5 ma incumat sa scriu toata matricea 20x20... cod sage:

sage: def A( n,p ): return matrix( IntegerModRing(p), n, n, [ [ i^j+j^i for i in [1..n] ] for j in [1..n] ] )
....:
sage: A(20,5)
20 x 20 dense matrix over Ring of integers modulo 5

sage: print A(20,5).str()
[2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1]
[3 3 2 2 2 0 2 0 3 4 4 0 1 0 3 2 1 3 4 1]
[4 2 4 0 3 0 0 3 2 4 3 4 0 3 2 2 1 1 1 1]
[0 2 0 2 4 2 0 2 0 1 0 2 0 2 4 2 0 2 0 1]
[1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0]
[2 0 0 2 1 2 0 0 2 1 2 0 0 2 1 2 0 0 2 1]
[3 2 0 0 2 0 1 3 1 4 4 4 4 3 3 2 0 1 2 1]
[4 0 3 2 3 0 3 2 4 4 3 2 4 0 2 2 4 0 3 1]
[0 3 2 0 4 2 1 4 3 1 0 3 2 0 4 2 1 4 3 1]
[1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0]
[2 4 3 0 1 2 4 3 0 1 2 4 3 0 1 2 4 3 0 1]
[3 0 4 2 2 0 4 2 3 4 4 2 3 0 3 2 3 0 4 1]
[4 1 0 0 3 0 4 4 2 4 3 3 1 3 2 2 0 2 1 1]
[0 0 3 2 4 2 3 0 0 1 0 0 3 2 4 2 3 0 0 1]
[1 3 2 4 0 1 3 2 4 0 1 3 2 4 0 1 3 2 4 0]
[2 2 2 2 1 2 2 2 2 1 2 2 2 2 1 2 2 2 2 1]
[3 1 1 0 2 0 0 4 1 4 4 3 0 3 3 2 4 2 2 1]
[4 3 1 2 3 0 1 0 4 4 3 0 2 0 2 2 2 3 3 1]
[0 4 1 0 4 2 2 3 3 1 0 4 1 0 4 2 2 3 3 1]
[1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0]
sage: A(20,5).rank()
8

Avem deci de-a face cu o matrice de rang 8, in cel mai bun caz avem deci
n(5) = 8, cel mai mic n pentru care minorul diagonal corespunzator poate avea determinant nenul. Intr-adevar,

sage: A( 8,5 ).det()
4

Sa facem cam acelasi lucru cu 7.
Nu mai tiparesc matricea cea mare...

sage: A( 7*6, 7 ).rank()
12
sage: A( 12, 7 ).rank()
12
sage: A( 12, 7 ).det()
1

Deci n(7) = 12 .

Bun, sa scriem atunci un mic program care face calculele corespunzatoare pentru noi...

cod

Rulez acest cod pana cand imi ingheata masina...
Pana in momentul de fata am dat de...


p=2 | A( 2, 2 ) are rang 2. | A( 2, 2 ) are rang 2. ... OK : n(2) = 2
p=3 | A( 6, 3 ) are rang 4. | A( 4, 3 ) are rang 4. ... OK : n(3) = 4
p=5 | A( 20, 5 ) are rang 8. | A( 8, 5 ) are rang 8. ... OK : n(5) = 8
p=7 | A( 42, 7 ) are rang 12. | A( 12, 7 ) are rang 12. ... OK : n(7) = 12
p=11 | A( 110, 11 ) are rang 20. | A( 20, 11 ) are rang 20. ... OK : n(11) = 20
p=13 | A( 156, 13 ) are rang 24. | A( 24, 13 ) are rang 24. ... OK : n(13) = 24
p=17 | A( 272, 17 ) are rang 32. | A( 32, 17 ) are rang 32. ... OK : n(17) = 32
p=19 | A( 342, 19 ) are rang 36. | A( 36, 19 ) are rang 36. ... OK : n(19) = 36
p=23 | A( 506, 23 ) are rang 44. | A( 44, 23 ) are rang 44. ... OK : n(23) = 44
p=29 | A( 812, 29 ) are rang 56. | A( 56, 29 ) are rang 56. ... OK : n(29) = 56
p=31 | A( 930, 31 ) are rang 60. | A( 60, 31 ) are rang 60. ... OK : n(31) = 60
p=37 | A( 1332, 37 ) are rang 72. | A( 72, 37 ) are rang 72. ... OK : n(37) = 72...

/home/dan/sage-4.3.1/sage-4.3.1-Ubuntu9.10-N270-i686-Linux/local/bin/sage-sage: line 206: 2863 Killed sage-cleaner
/home/dan/sage-4.3.1/sage-4.3.1-Ubuntu9.10-N270-i686-Linux/local/bin/sage-sage: line 206: 2864 Killed sage-ipython "$@" -i
dan@ardeal ~/sage-4.3.1/sage-4.3.1-Ubuntu9.10-N270-i686-Linux $

Se pare ca avem ceva de forma n(p) = 2p-2 ...
Pana aici nu putem vorbi de o generalizare. In cel mai bun caz ne aflam in cadrul experimental, la trecerea spre punctul in care cautam un motiv pentru care avem dependenta liniara intre liniile matricii infinite cu intrarile
( i, j ) --> i^j + j^i modulo p
incepand cu linia (2p-2)+1.
Cand gasim motivul, probabil ca inca suntem nevoiti sa gasim un motiv nou pentru faptul ca primele (2p-2) linii sunt independente (sau sa gasim un p care infirma aceasta conjectura optimista).

Ma opresc aici, trebuie sa ma leg de masa de seara.
Care este motivul pentru care poate sa ne intereseze aceasta problema?
(In matematica avem tocmai nenumarate probleme structurale care plang dupa o solutie rapida...)
Motivul NU poate fi numai "generalizarea" in sine.

In notatiile de mai sus se poate demonstra relativ usor

n(p) < 2p-1

folosind urmatoarea idee, pe care o ilustrez cel mai usor pe un caz particular.
(Mi-e greu sa scriu aici matrici generale cu 2p-1 linii si muuuulte coloane.)

Sa consideram cazul special p=5.
Ne uitam la matricea A cu intrari in ZZ modulo p, cu
2p-1 linii si
o infinitate de coloane
cu intrarile
A( i,j ) = i^j + j^i modulo p,
i de la 1 la 2p-1, j de la 1 incolo. Ea este
[2 3 4 0 .1. 2 3 4 0 .1. 2 3 4 0 .1. 2 3 4 0 .1... ]
[3 3 2 2 .2. 0 2 0 3 .4. 4 0 1 0 .3. 2 1 3 4 .1... ]
[4 2 4 0 .3. 0 0 3 2 .4. 3 4 0 3 .2. 2 1 1 1 .1... ]
[0 2 0 2 .4. 2 0 2 0 .1. 0 2 0 2 .4. 2 0 2 0 .1... ]
[1 2 3 4 .0. 1 2 3 4 .0. 1 2 3 4 .0. 1 2 3 4 .0... ]
[2 0 0 2 .1. 2 0 0 2 .1. 2 0 0 2 .1. 2 0 0 2 .1... ]
[3 2 0 0 .2. 0 1 3 1 .4. 4 4 4 3 .3. 2 0 1 2 .1... ]
[4 0 3 2 .3. 0 3 2 4 .4. 3 2 4 0 .2. 2 4 0 3 .1... ]
[0 3 2 0 .4. 2 1 4 3 .1. 0 3 2 0 .4. 2 1 4 3 .1... ]

Coloanele cu indicii p, 2p, 3p, ... sunt deosebite, de aceea le-am spatiat optic prin introducerea unor mici puncte "de ghidaj". Sa inmultim acum din stanga aceasta matrice cu matricea bloc (4+1+4) x (4+1+4) (in cazul particular),
( (p-1)+1+(p-1) ) x ( (p-1)+1+(p-1) ) in cazul general
1 0 0
0 1 0
-1 0 1
care este evident inversabila. Rangul ramane pe loc.
Explicit:
[1 0 0 0 .0. 0 0 0 0]
[0 1 0 0 .0. 0 0 0 0]
[0 0 1 0 .0. 0 0 0 0]
[0 0 0 1 .0. 0 0 0 0]
[0 0 0 0 .1. 0 0 0 0]
[4 0 0 0 .0. 1 0 0 0]
[0 4 0 0 .0. 0 1 0 0]
[0 0 4 0 .0. 0 0 1 0]
[0 0 0 4 .0. 0 0 0 1]
si acel 4 este de fapt un -1.
Dam de
[2 3 4 0 .1. 2 3 4 0 .1. 2 3 4 0 .1. 2 3 4 0 .1... ]
[3 3 2 2 .2. 0 2 0 3 .4. 4 0 1 0 .3. 2 1 3 4 .1... ]
[4 2 4 0 .3. 0 0 3 2 .4. 3 4 0 3 .2. 2 1 1 1 .1... ]
[0 2 0 2 .4. 2 0 2 0 .1. 0 2 0 2 .4. 2 0 2 0 .1... ]
[1 2 3 4 .0. 1 2 3 4 .0. 1 2 3 4 .0. 1 2 3 4 .0... ]
[0 2 1 2 .0. 0 2 1 2 .0. 0 2 1 2 .0. 0 2 1 2 .0....]
[0 4 3 3 .0. 0 4 3 3 .0. 0 4 3 3 .0. 0 4 3 3 .0....]
[0 3 4 2 .0. 0 3 4 2 .0. 0 3 4 2 .0. 0 3 4 2 .0....]
[0 1 2 3 .0. 0 1 2 3 .0. 0 1 2 3 .0. 0 1 2 3 .0....]

Primele cinci linii au ramas pe loc. Verdele a devenit oranj.
Ne uitam doar la liniile oranj. Periodicitatea este evidenta. Multele zerouri intermediare conduc repede la concluzia ca
[0 2 1 2 .0. 0 2 1 2 .0. 0 2 1 2 .0. 0 2 1 2 .0....]
[0 4 3 3 .0. 0 4 3 3 .0. 0 4 3 3 .0. 0 4 3 3 .0....]
[0 3 4 2 .0. 0 3 4 2 .0. 0 3 4 2 .0. 0 3 4 2 .0....]
[0 1 2 3 .0. 0 1 2 3 .0. 0 1 2 3 .0. 0 1 2 3 .0....]
are rangul < (p-1) . Ajunge de exemplu sa vedem o combinatie liniara intre liniile submatricii
[ 2 1 2 ]
[ 4 3 3 ]
[ 3 4 2 ]
[ 1 2 3 ]
pentru a conclude ca avem "aceeasi" combinatie liniara si pentru matricea oranj de dimensiuni (p-1) x infinit. Deci rangul matricii A de mai sus nu este maximal. Daca mai adaugam linii avem argumentul analog (sau reducerea..).

Avem in acest mod o inegalitate, n(p) este deci cel mult 2p-2.
Pentru a rezolva complet problema, trebuie sa mai lucram... Calculatorul ne face experimental sa avem incredere in relatia

Ramane sa o mai si demonstram!
(Mai sus, p > 2 prim.)