All Questions
Tagged with gaussian-elimination modular-arithmetic
12 questions
13
votes
5
answers
3k
views
Why does Gaussian elimination sometimes work in rings where it should not?
I think it's best to illustrate this with an example.
Take for instance the ring of integers modulo $6$. If I have the system of equations:
$$ \begin{aligned} 2x + 2y &= 4 \\ 3x + 4y &= 3 \end{...
- 141
-2
votes
1
answer
59
views
solutions of the simultaneous congruences
I need to find the solutions of the simultaneous congruences
$$
\begin{aligned}
3 x+3 z & \equiv 1\pmod 5, \\
4 x-y+z & \equiv 3\pmod 5 .
\end{aligned}
$$
How to reduce this into the following ...
- 542
3
votes
1
answer
1k
views
How do you go about Gaussian elimination modulo p?
The problem at hand is specifically to find the inverse of a matrix using Gaussian elimination modulo 29. I am familiar with the process of regular Gaussian elimination and modular arithmetic but not ...
- 49
1
vote
1
answer
95
views
Gauss elimination over $\mathbb{Z}_2$
I should solve this system of equations over $\mathbb{Z}_2$:
$3x_1 + x_2 + 2x_3 + x_4 = 2$
$-x_1 + x_2 + x_3 - x_4 = 1$
$-5x_1 + x_2 + 3x_3 + 3x_4 = 1$
So I tried to set up the matrix, which would be
$...
- 475
1
vote
0
answers
66
views
Please show steps using Gaussian Elimination to solve X for a set of modular linear equations
There is a linear system of 4 equations in field $Z_p$ with 4 unknowns $k_1$, $k_2$, $x_1$, $x_2$. The other variables s, r and h are known.
Please show me all the steps using Gaussian Elimination or ...
- 11
0
votes
0
answers
171
views
Solving $AX=B$ for partially unknown $B$
I am trying to solve multiple systems of linear equations over $n$ variables $AX=B$, where $B$ is partially unknown. Let us assume that $A$ has shape $n' \times n$, $X$ has shape $n \times m$ and $B$ ...
- 770
1
vote
0
answers
35
views
Solving a linear equation system in $\mathbb{Z}_q$, where $q$ prime
I am wondering about the following: Assume you have a linear equation system of the form:
$$Ax = b$$, where $A \in \mathbb{Z}_q^{n \times m}$, $x \in \mathbb{Z}_q^m$, $b \in \mathbb{Z}_q^n$
and we ...
- 161
1
vote
1
answer
92
views
inverse of a $2\times2$ matrix, Gaussian elimination with unknown $x$
$C=AB$ I need to find A so $CB^{-1}=A$ working in modulo 10
and C=$ \begin{bmatrix}2 & 5 \\3 & 1 \end{bmatrix}$ mod 10
with B=$ \begin{bmatrix}3 & 4 \\2 & x \end{bmatrix}$ ...
- 145
1
vote
1
answer
1k
views
inverse matrix with modulo
I have a $b1=(3,9)$ $b2=(9,x)$, working in modulo 10, where x is unknown and I need to find an inverse matrix so I use Gaussian elimination.
I wrote$ \begin{bmatrix}3 & 9 \\9 & x \end{...
- 145
2
votes
2
answers
3k
views
Inverting a matrix in $\mathbb{Z}/n\mathbb{Z}$.
So in my Linear Algebra course I was shown that we cannot directly use row reduction to invert a matrix over a commutative ring in general because the algorithm requires elements to be invertible (...
- 385
0
votes
1
answer
132
views
Count of solutions to matrix equations
Given these modular equations:
$$a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n = b_1 \bmod p $$
$$a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n = b_2 \bmod p $$
$$\vdots$$
$$a_{m,1} x_1 + a_{m,...
- 135
7
votes
1
answer
4k
views
How can I use Gauss elimination to solve equations with Modular arithmetics?
I've given some equations look like this.
$a_{1,1} x_1 + a_{1,2} x_2 + a_{1,3} x_3 + ... + a_{1,n} x_n\equiv 1 \mod p$
$a_{2,1} x_1 + a_{2,2} x_2 + a_{2,3} x_3 + ... + a_{2,n} x_n\equiv 1\mod p$
$...
- 103