Esercizio Sagemath applicazioni lineari

[paolo1712]

Salve a tutti, potreste dirmi perché questo codice mi genera sempre e solo funzioni suriettive? Avrei bisogno di generare funzioni $f:RR^m->RR^n$ casuali che rispettino sempre la condizione $m>n$ ma su cui devo fare la verifica della surgettività e nel caso continuare l'esercizio, viceversa altro.

Codice:

 while True:
        m = ZZ.random_element(1, 10)
        n = ZZ.random_element(1, 10) 
        if m > n:
            break
print("m =", m, ", n =", n)
A = random_matrix(SR, n, m)
show(A)
show('il rango di A è ', rank(A))
f=linear_transformation(A,side='right')
show(f)
f.is_surjective()

Inoltre se volessi scrivere l'applicazione esplicitandone la relazione funzionale (ad esempio $f(a,b,c)=(a+b,2c,a+c)$), teoricamente dovrei moltiplicare A per un vettore di variabili. Il problema è che non posso inizializzare un numero predefinito di variabili perché dipende da $n$. Allora avevo pensato questo

Codice:

alfabeto = 'abcdefghijklmnopqrstuvwxyz'
variabli = [var(alfabeto[i]) for i in range(n)]

ma non funziona. Cioè non posso scrivere

Codice:

f([variabili])

Vi ringrazio!

Piccola domanda scema. Perchè quando stampo show('il rango di A è ', rank(A)) dopo la "è" non mi lascia uno spazio anche se lo metto o anche se aggiungo show('il rango di A è',' ', rank(A))?

[Quinzio]

Ma che linguaggio e' ? E' Python ?
Puoi mettere il codice completo, se non sono 1 milioni di righe ?

Ti genera solo funzioni suriettive forse perche' la matrice viene riempita con dei floating point. Non saprei dire meglio.

[axpgn]

Vedi sagemath.org

[paolo1712]

@Quinzio è affine a python e credo poggi su di esso ma non ne sono sicuro. Il codice è lungo un centinaio di righe, non è per niente ottimizzato (non ho interesse nel farlo) però funziona.
In partica dapprima chiede se si vuole generare un'applicazione lineare partendo da due basi di spazi vettoriali e matrice assegnata. In caso affermativo chiede e verifica che le dimensioni degli spazi siano $m>n$ e raccoglie in input tutti i vettori.
In caso negativo (e quindi la parte che ho postato) chiede se si vuole generare un'applicazione lineare casuale a partire da una matrice casuale.
Dopodiché in base all'output, deve generarmi una funzione $g:RR^n->RR^m$ tale che $f o g=Id_(RR^m)$

Perché il fatto che venga riempita con floating point comporta ciò?

[Quinzio]

Perché il fatto che venga riempita con floating point comporta ciò?

Mi sono spiegato male. Mi correggo.
Non e' tanto il fatto che la matrice sia fatta con dei floating point, quanto piuttosto il fatto che la matrice sia casuale e ogni elemento sia random con un range molto ampio.
Idealmente la matrice e' riempita con dei numeri reali, ma ovviamente i numeri reali si possono rappresentare solo con i float in modo approssimativo.
Qui c'e' una discussione fatta in modo rigoroso su questo argomento:
https://math.stackexchange.com/question ... ary-matrix

If the matrix is over Q which are independently chosen and equally likely to be 0 or 1, then, when n becomes large, the probability that the matrix has full rank approaches 1.

In pratica ti dice che una matrice riempita con dei razionali casuali ha rango pieno. A maggior ragione se gli elementi sono reali.
A livello intuitivo per NON avere il rango pieno dovresti avere due righe che sono linearmente dipendenti.
Siccome hai a che fare con dei numeri casuali, e' abbastanza ovvio che tutte le righe sono indipendenti (e' molto probabile).

[apatriarca]

Se preferisci una spiegazione più pratica... Supponiamo di avere una matrice \(2 \times 2\) nel campo finito \(\mathbb Z/p\mathbb Z\) (quindi numeri interi in \([0, p-1]\))
\[
\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}
\]
e di chiederci quale sia il suo rango. Se \(a = 0,\) allora la matrice avrà rango massimo se \(c \neq 0.\) Se \(a \neq 0,\) allora è sufficiente avere \(d \neq (bc)a^{-1}\). La probabilità sarà quindi uguale a
\[ P(a = 0)\,P(c \neq 0) + P(a \neq 0)\,P(d \neq (bc)a^{-1}) = \frac{1}{p}\,\frac{p - 1}{p} + \frac{p-1}{p}\frac{p - 1}{p} = \frac{p^2 - p}{p^2} = \frac{p - 1}{p}. \]
Quindi nel caso di \(p=3\) abbiamo ad esempio \(2/3 = 0.\overline{6}\). Se prendiamo \(p=11\) abbiamo già \(0.\overline{90}\). È quindi chiaro che se passiamo ad un numero di valori ancora maggiori come nei floating point (o addirittura in \(\mathbb Q\) o \(\mathbb Q\)) la probabilità tenderà ad \(1\). Nella pratica, con matrici che non sono casuali, può in realtà capitare di avere in effetti matrici singolari (o "quasi singolari").

Con l'aumento delle dimensioni della matrice le probabilità di avere matrici singolari diminuisce ulteriormente come si vede nel caso di \(p = 2\) nella discussione postata da Quinzio.

NOTA: Quello che ho scritto non era corretto.

[paolo1712]

Vi ringrazio!
Per avere rango massimo nel caso in cui $a=0$, perché non è necessario supporre che anche $b!=0$ ?

Immagino quindi non ci sia soluzione se non ridurre le dimensioni notevolmente o fare in modo che ci sia una riga/colonna di soli zeri. Però in ogni caso renderei la matrice "meno casuale".
O ancora ma credo allungherei il brodo a dismisura, potrei dividere la matrice in vettori riga, moltiplicarli per un elemento random intero tra 0 e 1 e ricostruire la matrice. Però così verrebbe fuori quasi sempre una funzione non suriettiva.

[Quinzio]

Vi ringrazio!
Per avere rango massimo nel caso in cui $a=0$, perché non è necessario supporre che anche $b!=0$ ?

In realta' quella formula non da la probabilita' corretta.
Ad es. nel caso che gli elementi della matrice siano solo 0, 1, questi sono i casi di a, b, c, d che rendono la matrice 2x2 singolare.

Codice:

a b c d
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
10

E in tutto sono 10 su 16.

Immagino quindi non ci sia soluzione se non ridurre le dimensioni notevolmente o fare in modo che ci sia una riga/colonna di soli zeri. Però in ogni caso renderei la matrice "meno casuale".
O ancora ma credo allungherei il brodo a dismisura, potrei dividere la matrice in vettori riga, moltiplicarli per un elemento random intero tra 0 e 1 e ricostruire la matrice. Però così verrebbe fuori quasi sempre una funzione non suriettiva.

Non e' che la matrice sia "meno casuale".
Se uno imposta certe condizioni, quelle sono.
Se ad es. lancio 2 dadi e voglio che uno sia uguale a 6, il risultato e' sempre casuale, solo che ha distribuzione diversa.

[apatriarca]

In effetti ci ho pensato un po' velocemente e ho commesso degli errori. La probabilità che una matrice sia non singolare è comunque effettivamente tendente a \(1\) con l'aumentare di \(p\) per quanto la formula fosse errata. Nel seguito calcolo però per comodità la probabilità inversa, cioè che la matrice sia singolare.

Abbiamo che una matrice \(2 \times 2\) è singolare se il suo determinante \(ad - bc\) è uguale a zero. Abbiamo due casi:
1. \(ad = bc = 0\). Abbiamo che almeno uno tra \(a\) e \(d\) e almeno uno tra \(b\) e \(c\) devono essere zero. Una volta scelta una coppia tra le quattro possibili, abbiamo \(p^2\) scelte per gli altri due valori. A questo valore dobbiamo togliere i casi contati doppi di triplette di zeri (ce ne sono \(4p\)) e aggiungere il caso di quattro zeri. In totale abbiamo quindi \(4p^2 - 4p + 1\) matrici.
2. \(ad = bc \neq 0\). In questo caso abbiamo che tutti i valori devono essere diversi da zero e il quarto valore è fissato dagli altri \(3\). Quindi ci sono \((p - 1)^3\) matrici singolari in questo caso.

In totale abbiamo insomma \(p^3 + p^2 - p\) matrici singolari. Abbiamo in totale \(p^4\) matrici e quindi la probabilità dovrebbe insomma essere
\[\frac{p^3 + p^2 - p}{p^4}\]
La funzione ha un massimo in \(1\) uguale a \(1\) e scende monotonicamente con il limite all'infinito di \(0\). Nel caso \(p = 2\) vale \(10/16 = 0.625\) Per \(p = 3\) value \(33/81 = 0.\overline{407}\) e per \(p = 11\) vale \(131/1331 \approx 0.098\).

[paolo1712]

tutto chiaro, vi ringrazio ancora