Citat:
Ursprungligen postat av en kopp kaffe
Med
dim ker(A) menar du antalet linjärt oberoende vektorer sådana att
Ax = 0? Jag vill lösa det genom att finna en matris B av med
k rader och
d kolumner så att
AB = nollmatrisen. Något i stil med
Pr[dim ker(A) = d] = Pr[AB = nollmatrisen]Pr[det B != 0]
Så #sätt att välja B på utan restriktion är
2^{kd}. Sätten att välja B med linjärt oberoende kolumner är
(2^k - 1)(2^k - 2)(2^k - 2^2)...(2^k-2^{d-1}) = 2^{kd} prod_{i=1}^{d-1}(1-2^{i-k}
Följaktligen
Pr[
det B != 0] =
prod_{i=1}^{d-1}(1-2^{i-k}.
Tycker dock att jag hamnar i samma svårigheter som tidigare när jag skall beräkna
Pr[
AB = nollmatrisen]... antar att det inte är bästa sättet att gå tillväga på

Jag har lite för dålig koll på satser inom matristeori för att kunna se att det går att göra på annat sätt dock.
Vad är B här? En slumpmatris? Om inte, vad betyder
Pr[
det B != 0]? Hursomhelst, eftersom B inte är kvadratisk, vad betyder det B?
Nej, jag är inte säker på att den idén funkar. Jag skulle göra såhär istället:
Vi vill alltså räkna ut fördelningen för dim ker(A). Eftersom
dim ker(A) = n - rk(A) så är det ekvivalent att räkna ut en fördelning för rk(A).
Låt N(r; k, n) beteckna antalet k x n-matriser (över GF(2)) med rang r. Det är detta vi vill räkna ut.
Säg att vi har k x n-matris av rang r. Detta betyder att de n kolonnerna i matrisen spänner upp ett delrum av dimension r. Det finns två fall:
(a) Antingen spänner de första n-1 kolonnerna i matrisen upp ett delrum av dimension r, eller
(b) så spänner de upp ett delrum av dimension r.
I fall (a) finns det N(r; k, n-1) möjliga sätt att välja de första n-1 kolonnerna. Den sista kolonnen måste väljas så att den är en vektor i det delrummet som spänns upp av de första n-1 kolonnerna (annars får hela matrisen rang r+1), så detta kan göras på 2^r. Totalt finns alltså 2^r N(r; k, n-1) olika matriser i fall (a).
I fall (b) finns det N(r-1; k, n-1) möjliga sätt att välja de första n-1 kolonnerna. Den sista kolonnen måste väljas så att den är en vektor som
inte är i det delrummet som spänns upp av de första n-1 kolonnerna. Detta kan alltså göras på 2^k - 2^r sätt. Så totalt finns (2^k - 2^r) N(r-1; k, n-1) fall här.
Så vi får alltså rekursionsrelationen
N(r; k, n) = 2^r * N(r; k, n-1) + (2^k - 2^r) * N(r-1; k, n-1).
Det känns inte helt omöjligt att lösa denna för att få ett uttryck för N(r; k, n) på någorlunda sluten form. Gör man det är det lätt att räkna ut sannolikheten att en matris har en viss rang.