Matrices with fixed row and column sums

[This article was first published on Saturn Elephant, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Given two vectors \(p\) and \(q\) of non-negative integer numbers, denote by \(A(p, q)\) the number of matrices with non-negative integer entries whose row sum and column sum respectively are \(p\) and \(q\), and denote by \(B(p, q)\) the number of matrices with entries in \(\{0, 1\}\) whose row sum and column sum respectively are \(p\) and \(q\).

The problem of determining \(A(p,q)\) and \(B(p,q)\) has a solution in the theory of symmetric polynomials. Denote by \(\lambda\) the vector obtained by sorting \(p\) in decreasing order and dropping the zero elements, and similarly, denote by \(\mu\) the vector obtained by sorting \(q\) in decreasing order and dropping the zero elements. Then \(\lambda\) and \(\mu\) are two integer partitions. In order for the two numbers \(A(p,q)\) and \(B(p,q)\) to be non-zero, an obvious necessary condition is that the sum of \(p\) is equal to the sum of \(q\). Let’s assume this condition holds true and denote by \(n\) this common sum. Of course, \(n\) is also the sum of \(\lambda\) and the sum of \(\mu\).

Then it is known in the theory of symmetric polynomials that \[ A(p, q) = \sum_{\kappa \vdash n} K(\kappa, \lambda)K(\kappa, \mu) \] where the notation \(\kappa \vdash n\) means that \(\kappa\) is an integer partition of \(n\) and where \(K(\kappa, \nu)\) denotes the Kostka number associated to two integer partitions \(\kappa\) and \(\nu\).

It is also known that \[ B(p, q) = \sum_{\kappa \vdash n} K(\kappa, \lambda) K(\kappa’, \mu) \] where \(\kappa’\) denotes the conjugate partition (or dual partition) of the partition \(\kappa\).

One also has \(A(p,q) = \langle h_\lambda, h_\mu \rangle\) where \(h_\kappa\) denotes the complete homogeneous symmetric function associated to an integer partition \(\kappa\) and \(\langle \cdot, \cdot \rangle\) denotes the Hall inner product, and one has \(B(p,q) = \langle h_\lambda, e_\mu \rangle\) where \(e_\kappa\) denotes the elementary symmetric function associated to an integer partition \(\kappa\).

All these results can be found in Macdonald’s book Symmetric functions and Hall polynomials.

Now let’s turn to the implementation of \(A(p,q)\) and \(B(p,q)\) in R. Enumerating the partitions of an integer is one of the features of the partitions package (the parts function). This package also allows to get the conjugate partition of an integer partition (the conjugate function). The Kostka numbers can be obtained with the syt package (the KostkaNumber function). So we use these two packages.

library(partitions)
library(syt)

Apq <- function(p, q) {
  n <- sum(p)
  if(sum(q) != n) {
    return(0L)
  }
  lambda <- Filter(\(i) {i > 0}, sort(p, decreasing = TRUE))
  mu <- Filter(\(i) {i > 0}, sort(q, decreasing = TRUE))
  partitions <- parts(n)
  sum(apply(partitions, 2L, function(kappa) {
    KostkaNumber(kappa, lambda) * KostkaNumber(kappa, mu)
  }))
}

Bpq <- function(p, q) {
  n <- sum(p)
  if(sum(q) != n) {
    return(0L)
  }
  lambda <- Filter(\(i) {i > 0}, sort(p, decreasing = TRUE))
  mu <- Filter(\(i) {i > 0}, sort(q, decreasing = TRUE))
  muprime <- conjugate(mu)
  partitions <- parts(n)
  sum(apply(partitions, 2L, function(kappa) {
    KostkaNumber(kappa, lambda) * KostkaNumber(kappa, muprime)
  }))
}
To leave a comment for the author, please follow the link and comment on their blog: Saturn Elephant.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)