<p>Suppose we are given a linear equation <span class="math-container">$ Ax=b $</span>, where <span class="math-container">$ A \in Z_q^{n \times m} $</span> and <span class="math-container">$ b \in Z_q^n $</span>.</p>
<p>Note that <span class="math-container">$ q $</span> is a prime here, and <span class="math-container">$ Rank(A)= Rank(A;b)=n&lt;m $</span>.</p>
<p>I wonder whether the following <strong>ROUCHÉ–CAPELLI THEOREM</strong>
still holds in the finite field <span class="math-container">$ Z_q $</span>:</p>
<p>Given a system of linear equations, <span class="math-container">$ Ax = b $</span>, it holds that:</p>
<ol>
<li><span class="math-container">$ Rank(A) = Rank(A; b) $</span> ⇔ the system is unsolvable.</li>
<li><span class="math-container">$ Rank(A) = Rank(A; b) $</span> ⇔ the system is solvable.</li>
<li><span class="math-container">$ Rank(A) = Rank(A; b) = m $</span> ⇔ the system has unique solution.</li>
<li><span class="math-container">$ Rank(A) = Rank(A; b) &lt; m $</span> ⇔ the system has infinite solutions.</li>
</ol>
<p>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.</p>
<p>Thanks.</p>

CC BY-SA 4.0
2022-10-31T15:05:36.110Z
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.
holf
CC BY-SA 4.0
2022-10-31T21:34:34.023Z
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.
D.W.
<finite-fields><linear-equations>
Solving Linear Equations over finite field $ Z_q $
Jeremy Smith
# Solving Linear Equations over finite field $ Z_q $

(Asked by: username_0 on 2022-10-31)

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.

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.

**Tags:** finite-fields, linear-equations
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 0 answers

