Wikipedia:Reference desk/Archives/Mathematics/2021 October 18

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 18

Counting permutations in the nullspace of a matrix

Given a matrix $M$ (size $m\times n$) and a matrix $N$ (size $n\times 1$, with entries in (0, 1)), is there a linear algebra type way to count the number of distinct permutations of $N$ such that $M*N_{permuted}=0$? For example, with

$M={\begin{bmatrix}-1&-1&0&1&-1&0\\1&0&-1&-1&0&1\\\end{bmatrix}},N={\begin{bmatrix}1&1&0&0&0&0\end{bmatrix}}^{\intercal }$

then the answer would be 2 with ${\begin{bmatrix}1&0&0&1&0&0\end{bmatrix}}^{\intercal }$ and ${\begin{bmatrix}0&0&1&0&0&1\end{bmatrix}}^{\intercal }$. 174.73.241.150 (talk) 01:35, 18 October 2021 (UTC)

I don't see how to establish this in any formal or semi-formal way, but my mathematical instinct makes me expect that the operations of linear algebra will not help to count these permutations. If $M$ is a null matrix, and $w$ is the weight of $N$, the number of permutations for which the product is the null vector equals $\textstyle {\binom {n}{w}}.$ I do not see a plausible way how that would be, for example, the permanent of some matrix that is a function of $M$ (which is null) and $N.$  --Lambiam 05:58, 18 October 2021 (UTC)

Yes, the number of permutations of N is finite so this seems to fall under the domain of discrete programming rather than linear algebra. I strongly suspect the problem can be stated in way that's NP-hard. For example if N is a 0-1 matrix then you essentially have a 0-1 programming problem; it seems unlikely that the special case we're dealing with here would make the problem significantly easier. --RDBury (talk) 11:07, 18 October 2021 (UTC)