0
$\begingroup$

Suppose we are given a linear equation $ Ax=b $, where $ A \in Z_q^{n \times m} $ and $ b \in Z_q^n $.

Note that $ q $ is a prime here, and $ Rank(A)= Rank(A;b)=n<m $.

I wonder whether the following ROUCHÉ–CAPELLI THEOREM still holds in the finite field $ Z_q $:

Given a system of linear equations, $ Ax = b $, it holds that:

  1. $ Rank(A) = Rank(A; b) $ ⇔ the system is unsolvable.
  2. $ Rank(A) = Rank(A; b) $ ⇔ the system is solvable.
  3. $ Rank(A) = Rank(A; b) = m $ ⇔ the system has unique solution.
  4. $ Rank(A) = Rank(A; b) < m $ ⇔ the system has infinite solutions.

Is there any standard theorem in the thesis or textbook if it does? I need to cite the standard theorem into my thesis, but I can't find any.

Thanks.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ How could you have an infinite number of solution when you only have a finite number of vectors of dimension $m$? Anyway, by the very definition of the rank (on any vector space, thus on vector space over $Z_q$ too), Rank(A)=Rank(A;b) exactly says that $b$ is linearly dependent on the column of $A$. Now, if you have a solution $x_0$, your set of solution is in one to one correspondence with $x_0+Ker(A)$, so you can deduce the number of solution from there. $\endgroup$
    – holf
    Oct 31, 2022 at 15:05
  • 3
    $\begingroup$ This looks like a question about pure math, with no computer science knowledge needed to answer it. As such it does not seem on-topic here. $\endgroup$
    – D.W.
    Oct 31, 2022 at 21:34

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.