Given a matrix $M$ that consists of a set of $4K$ binary row vectors (each vector entry is 0 or 1) each of length $K$. Moreover, it is known/promised that no subset of rows in matrix add to an all 1 vector. For a given integer $X$, the only the following operations permitted on the rows of the matrix:


1. Modular addition: $r\_i = (r\_i\*u+ r\_j\*v)\%X$, for some integers $u, v$


**Objective:** Using the above two operations, transform a row into an all 1 vector (whenever it is possible). Is this achievable? My guess is yes (using a process similar to Gaussian Elimination) but need a reconfirmation.


Let us choose 2 random prime numbers $P\_1$ and $P\_2$ ($P\_1$ < $P\_2$) as $X$.


**Query 1:** Is it possible that there exists instances of $M$, that (using the above 2 operations) we can transform a row to an all 1 vector for $P\_1$, but the same will not be possible for $P\_2$?


**Query 2:** For each given instance of $M$, is there some value $V$ beyond which for all (prime) $X$, the above 2 operations will always be able to result in an all 1 vector?


Moreover, is for any given matrix $M$ and $X$ is there a general property that we can always test or state that is true iff such a row transformation is possible?


Can someone please help with this (along with examples for both queries if possible)?



A query about modular arithmetic on a matrix
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](https://en.wikipedia.org/wiki/Rouch%C3%A9%E2%80%93Capelli_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](https://en.wikipedia.org/wiki/Smith_normal_form#Definition) 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).


