Return to Answer

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)$.

If $M'$ has rank $r$ over reals, then the equation is insoluble over ${\rm GF}(X)$ iff $X$ divides the $r$-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 (this includes matrices of full rank over reals).

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)$.

It follows that for a prime $X$, the equation is insoluble over ${\rm GF}(X)$ iff $X$ divides the $r$-th determinant divisor of $M$ but not of $M'$ for some $r$ (the largest such $r$ is the rank of $M'$ over ${\rm GF}(X)$). 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 (including matrices of full rank over reals).

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

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)$.

If $M'$ has rank $r$ over reals, then the equation is insoluble over ${\rm GF}(X)$ iff $X$ divides the $r$-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 (this includes matrices of full rank over reals).

The question is equivalent to finding integer vector $x$ such that $$xM = \iota_K,$$ where $\iota_k$ is the all-1 vector of length $K$, which is considered over the field ${\rm GF}(X)$ for a prime $X$.

By Rouché–Capelli theorem, this equation has a solution iff the rank of $M$ equals the rank of $M$ augmented with additional row $\iota_k$ (denote this matrix $M'$).

Let's assume $M$ has a full rank over reals, ie. $\mathrm{rank}(M)=K$. Then the equation does not have solution 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 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).

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