Given a matrix ${\displaystyle M}$ (size ${\displaystyle m\times n}$) and a matrix ${\displaystyle N}$ (size ${\displaystyle n\times 1}$, with entries in (0, 1)), is there a linear algebra type way to count the number of distinct permutations of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle N} such that ${\displaystyle M*N_{permuted}=0}$? For example, with

${\displaystyle 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 ${\displaystyle {\begin{bmatrix}1&0&0&1&0&0\end{bmatrix}}^{\intercal }}$ and ${\displaystyle {\begin{bmatrix}0&0&1&0&0&1\end{bmatrix}}^{\intercal }}$. 174.73.241.150 ( talk) 01:35, 18 October 2021 (UTC) reply

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 ${\displaystyle M}$ is a null matrix, and ${\displaystyle w}$ is the weight of ${\displaystyle N}$, the number of permutations for which the product is the null vector equals ${\displaystyle \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 ${\displaystyle M}$ (which is null) and ${\displaystyle N.}$  -- Lambiam 05:58, 18 October 2021 (UTC) reply

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) reply