[math-fun] a month in the laboratory
can often save an afternoon in the library. I seem to have convinced myself that the probability that an nxn bitmatrix will have (mod 2) rank = k is 2 n - k + 1 k + 1 (n - k) (p ; p) (p ; p) p k n - k P(n,k) := -------------------------------------------, (p; p) n - k if the entries are 1 with probability p. Thus the peculiar base p identity Sum P(n,k) = 1. k In particular, the probability of being nonsingular is just (p;p)_n. Can someone tell me whose wheel I have reinvented? --rwg PS to anyone still running my Macsyma ehancements: Is ROW_REDUCE a no-op? It was on my machine until I replaced (defun $row_reduce (x) ...) with (define-autoload "c:\\rwg\\climax\\algebra\\matrix" $row_reduce) in /macsyma/macsyma2/system/init.lsp .
Oops, I think I switched p and q. Should have said ... the probability that an nxn bitmatrix will have (mod 2) rank = k is 2 n - k + 1 k + 1 (n - k) (q ; q) (q ; q) q k n - k P(n,k) := -------------------------------------------, (q; q) n - k if the entries are 1 with probability p = 1-q . Thus the peculiar base q identity Sum P(n,k) = 1. k In particular, the probability of being nonsingular is just (q;q)_n. Sorry for the noise, --rwg
I said
the probability that an nxn bitmatrix will have (mod 2) rank = k is
2 n - k + 1 k + 1 (n - k) (q ; q) (q ; q) q k n - k
P(n,k) := -------------------------------------------, (q; q) n - k
if the entries are 1 with probability p = 1-q .
More generally, for an m x n matrix, m - k + 1 k + 1 (m - k) (n - k) (q ; q) (q ; q) q k n - k P(m, n, k) = --------------------------------------------------. (q; q) n - k But transposing a matrix preserves its rank. P(m,n,k) = P(n,m,k)?? Yes! Exercise: write P(m,n,k) symmetrically in m and n. (Answer (much nicer) below)
Thus the FAR FROM peculiar base q identity
Sum P(m,n,k) = 1. k George Andrews gently pointed out that this is merely a case of the q Chu-Vandermonde identity, a terminating q-extension of Gauss's 2F1[1]. The reason I missed it was Macsyma's TERMRATIO failing to reduce terms(k) like (c547) product(f(i+k),i,a+k,2*k) 2 k /===\ | | (d547) | | f(k + i) | | i = k + a to rational functions of f. But with the latest patch, (c548) expand(termratio(%,k)) f(3 k + 1) f(3 k + 2) f(3 k + 3) (d548) -------------------------------- f(2 k + a) f(2 k + a + 1) --rwg Answer: -m -n m n + k (q , q ; q) q k P(m, n, k) = ----------------------- (q; q) k This surprised me. Can one get it by transforming the Pochhammers?
participants (1)
-
R. William Gosper