Skip to main content
2 of 4
added 13 characters in body; deleted 27 characters in body
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

The question is equivalent to finding an integer vector $x$ such that $$xM = \iota_K,$$ where $\iota_k$ is the all-1 vector of length $K$.

By Rouché–Capelli theorem, this equation has a solution modulo prime $X$ iff the rank of $M$ equals the rank of $M$ augmented with additional row $\iota_k$ (denote this matrix $M'$) over the field ${\rm GF}(X)$.

Let's assume $M$ has a full rank over reals, ie. $\mathrm{rank}_{\mathbb{R}}(M)=K$. Then the equation is insoluble over ${\rm GF}(X)$ iff $X$ divides the $K$-th determinant divisor of $M$ but not of $M'$. This provides answers to your queries:

Q1: Yes. The simplest example is $K=3$ with matrix composed of vectors $(0,1,1)$, $(1,0,1)$, $(1,1,0)$ each taken in 4 times. Then the equation has a solution over ${\rm GF}(X)$ for each prime $X$, except for $X=2$.

Q2: This is true only for matrices for which the equation is soluble over reals (eg., for matrices of full rank over reals).

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152