Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
> Hvis man nu i stedet kigger på matricer over legemet F_p (altså
> legemet med p elementer, p et primtal) er der lige pludselig kun
> endeligt mange n×n-matricer (faktisk præcis p^{n^2}), og da "en del"
> af disse er singulære, er sandsynligheden P(n, p) for at en tilfældig
> matrix i Mat_n(F_p) er invertibel strengt mindre end 1.
Hvad med følgende:
Vi vælger matricen ved en søjle ad gangen at smide tilfældigt valgte
(og ligefordelte) elementer ind på indgangene. Så snart vi véd at
søjlerne ikke er lineært uafhængige stopper vi.
I første søjle mister vi med det samme invertibilitet hvis og kun hvis
søjlen er 0. Det vil sige at sandsynligheden for at overleve første
søjle er 1-(1/p^n) = 1-(1/p)^(-n).
Hvis vi overlever første søjle, er sandsynligheden for at tabe i anden
søjle p/p^n (idet vektorrummet udspændt af den første søjle har
netop p elementer). Sandsynligheden for at *overleve* anden søjle er
derfor 1-(p/p^n) = 1-(1/p)^(n-1).
Tilsvarende er sandsynligheden for at overleve tredje søjle 1-(1/p)^(n-2).
Sandsynligheden for at finde en hel invertibel matrix bliver
P(Inv) = (1-(1/p)^n)*(1-(1/p)^(n-2))*...*(1-(1/p)^1)
> Jeg behøver ikke et eksplicit funktionsudtryk, men jeg er interesseret
> i den asymptotiske opførsel når n og/eller p [p^k] bliver stor.
Udtrykket ovenfor er et polynomium i 1/p, så når p bliver stor kan vi
vel nøjes med leddene af lavest grad, og dem kan vi forholdsvis nemt
finde ved håndkraft. Her er indtil tiende grad, (hvis altså n>10):
P(Inv) = 1 - (1/p) - (1/p)² + (1/p)^5 + (1/p)^7 + ...
Koefficientfølgen er i almindelighed Sloane's A010815. [1] Sloane
giver en lukket formel for koefficienter af grad op til n:
a(n) = (-1)^m if n is of the form m(3m+-1)/2; otherwise a(n)=0.
Idet alle koefficienter her er numerisk højst 1, kan vi nok gå ud fra
at P(Inv) er forholdsvis upåvirket hvis vi lader n vokse sig stor.
[1]
http://www.research.att.com/projects/OEIS?Anum=A010815
> Hvad hvis man erstatter p med p^k?
Ovenstående forudsætter kun at legemet er endeligt.
--
Henning Makholm "... not one has been remembered from the time
when the author studied freshman physics. Quite the
contrary: he merely remembers that such and such is true, and to
explain it he invents a demonstration at the moment it is needed."