Written: Oct. 27, 2023

In fond memory of Eugenio Calabi (May 11, 1923 - September 25, 2023), and Herbert Saul Wilf (June 13, 1931 - January 7, 2012)

In their beautiful note, "On the Sequential and Random Selection of Subspaces over a Finite Field", geometrical giant Eugenio Calabi and combinatorial giant Herb Wilf proposed an elegant algorithm to do what is promised in their title. In the present note, written forty six years later, we describe a Maple package, written by the second author, that implements their beautiful algorithm, and then go on to report numerous experiments, performed by the first author, that demonstrate the efficiency and reliability of the Calabi-Wilf algorithm.

Maple package

• CalabiWilf.txt, a Maple package that implements, and experiments with, the Calabi-Wilf algorithm for random generation of k-dimensional subspaces of GF(q)ⁿ

Sample Input and Output for CalabiWilf.txt

---

• If you want to see an article about estimating the average, variance, and central scaled moments up to the, 4, for the number of occurences of the submatrix, [[1]] (aka 1), in row-echelon matrices of dimension k by 2 k, matrices over GF(2), for k from, 50, to , 100, by simulating, 1000 times, using the amazing Calabi-Wilf algorithm for randomly generating a k-subspace of GF(2)^n
  the input gives the output.

• If you want to see an article about estimating the average, variance, and central scaled moments up to the, 4, for the number of occurences of the submatrix, [[1,0,2],[1,0,2],[1,0,1]], in row-echelon matrices of dimension k by 3k, matrices over GF(3), for k from, for k from, 50, to , 60, by simulating, 1000 times, using the amazing Calabi-Wilf algorithm for randomly generating a k-subspace of GF(3)^n
  the input gives the output.

  ---

• If you want to see an article about estimating of the average, variance, and central scaled moments up to the, 4, for the number of occurences of the number of ONES in row-echelon matrices of dimension k by , 2k, matrices over GF(3) for k from, 50, to , 55 ,by simulating, 1000, times using the amazing Calabi-Wilf algorithm for randomly generating a k-subspace of GF(3)^n and comparing it to the exact values
  the input gives the output.

• If you want to see an article about comparing the estimates of the average number of ONES in row-echelon matrices of dimension k by , 3 k, matrices over GF(2) for k from, 100, to , 110, by simulating, 1000, times, using the amazing Calabi-Wilf algorithm for randomly generating a k-subspace of GF(q)^n and comparing it to the exact values
  the input gives the output.

• If you want to see an article on the Minimal Weight of vectors in k-dimensional subspaces of GF(q)^n for k from 1 to, 5, q=2, and n from , 10, to , 100, in increments of, 10
  the input gives the output.

  ---

• If you want to see the smallest minimal weight and largest minimal weights, as well as the estimated average (and variance, and skewness and kurtosis) of the minimal weight in a random k-dimensional subspace of GF(2)^(2k) upon sampling 50000 random such subspaces using the Calabi-Wilf algorithm, then

  • for k=4, the input gives the output

  • for k=6, the input gives the output

  • for k=8, the input gives the output

  • for k=10, the input gives the output

  • for k=12, the input gives the output

  • for k=14, the input gives the output

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page