Citat:
Ursprungligen postat av dbshw
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
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.
Jag är slarvig, med det B != 0 menade jag att samtliga kolumner var oberoende. Skulle väl kunna ses som att det existerar en kvadratisk delmatris B' där det B' != 0.
På b), blir det inte #fall = (2^k - 2^{r-1}) N(r-1; k, n-1) ? Det är ju r-1 oberoende kolumner vi skall undvika linjärkombinationer av, inte r...?
Annars, snygg lösning!
