1
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ Operation 1 is a partial case of Operation 2 (since for any number $u$ we have a positive $u'$ such that $u\equiv u'\pmod X$). Also, the requirement for $u,v$ being positive can be dropped. $\endgroup$
    – Max Alekseyev
    Commented Oct 22, 2022 at 10:49
  • $\begingroup$ @MaxAlekseyev Thank you. Please consider the general case then (since both are equivalent) $\endgroup$
    – xyz
    Commented Oct 22, 2022 at 11:01
  • $\begingroup$ can someone please help with this ? $\endgroup$
    – xyz
    Commented Oct 23, 2022 at 12:34
  • $\begingroup$ can you edit the question in line with @MaxAlekseyev's comments above so it is stated with the minimum required conditions? $\endgroup$
    – kodlu
    Commented Oct 24, 2022 at 11:48
  • $\begingroup$ updated........ $\endgroup$
    – xyz
    Commented Oct 24, 2022 at 14:17

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you very much. Few clarifications: As I understand the R-C theorem provides a test whenever the system will have a solution. I am unclear about the second "Let us assume.." part: Does this test of insolubility works only when $M$ has a full rank and fails otherwise when $M$ does not have a full rank? Or the insoluble scenario arises iff $M$ has a full rank and thus this test is self-sufficient for all scenarios? $\endgroup$
    – xyz
    Commented Oct 23, 2022 at 19:16
  • $\begingroup$ And a follow up query: Is there a scenario where: Given a matrix M such that there are no subset of rows which add up to all 1 rows. But, $xM=ιK,$ can be solved for all primes $X$? Can we have a test or property that characterizes such matrices completely? $\endgroup$
    – xyz
    Commented Oct 23, 2022 at 19:41
  • $\begingroup$ @xyz: Full-rank matrices are just an example, I've corrected the answer to avoid confusion. As for scenario when the equation soluble modulo all primes, it takes place when the ranks over reals of $M$ and $M'$ are equal, and the radicals of $k$th determinant divisors of $M$ and $M'$ are the same for each $k$. $\endgroup$
    – Max Alekseyev
    Commented Oct 24, 2022 at 13:25
  • $\begingroup$ thanks again. Is there a small non trivial example (soluble modulo all primes) to make things clearer that satisfies these conditions, namely: (1) subset of rows don't add up to 1 vector (2) Ranks of $M$ and $M'$ are equal (3) Radicals of of $kth$ determinant divisors of $M$ and $M′$ are the same for each $k$? $\endgroup$
    – xyz
    Commented Oct 24, 2022 at 14:22
  • $\begingroup$ @xyz: A small non-trivial example is given by $M$ with a solution over integers. For example, $M$ containing vectors $(0,1,1)$, $(1,1,0)$, and $(0,1,0)$ has a solution $(1,1,p-1)$ for any prime $p$. $\endgroup$
    – Max Alekseyev
    Commented Oct 24, 2022 at 14:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .