0
votes
0answers
22 views

Testing for Linear Independence/rank mod m

I am working on cracking a hill cypher using modular linear algebra. Every example I have found online makes a big assumption that is not necessarily the case, and as I see it leaves a lot to be ...
6
votes
1answer
61 views

Matrix restoring (modulo n)

Let $m,n\geqslant 2$, and $A\in \mathcal{M}_n(\mathbb Z)$ such that $\det A \equiv 1 \pmod m$. Does it (necessarily) exist $M\in \mathrm{GL}_n(\mathbb Z)$ such that $A\equiv M \pmod m$?
1
vote
1answer
24 views

Bound on the degree of a determinant of a polynomial matrix

I want to implement a modular algorithm for computing the determinant of a square Matrix with multivariate polynomials in $\mathbb{Z}$ as components (symbolically). My idea is first to reduce the ...
0
votes
1answer
33 views

Solving two variables system equations with parameter above $\mathbb{Z}_7$

Let: $$(1+5a)x +y = 1$$ $$a^2x + y = 2$$ Eliminating the $y$ variable we have: $$(-a^2 +5a +1)x = 6$$ Now, I should have find $y$ such that $(-a^2 +5a +1)y = 1$, but obvoiusly I can't do that ...
0
votes
1answer
20 views

Linear equation with residue classes

I'm having a hard time solving an exercise that seems fairly easy: Given a linear map $$ f: (Z/5)^2 \mapsto (Z/5)^2 $$ and $$ f(\bar{2}, \bar{3}) = (\bar{1},\bar{1})$$ $$f(\bar{1}, \bar{4}) = ...
1
vote
1answer
30 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics experts

We have some attempt to numerically solve this math problem, which means that we like to count the number of independent solutions of this set of six of modular N algebraic equations: $$ (1) x_1 ...
0
votes
1answer
47 views

System of linear equations over $\mathbb{Z}_p$

Something like this: $$ \begin{cases} x_1+4x_4=1\\ x_1+2x_2+4x_3=3\\ 2x_1+2x_2+x_4=1\\ x_1+3x_3=2 \end{cases} $$ over $\mathbb{Z}_5$ I'm fine with solving it in regular $\mathbb{Z}$ but have no idea ...
1
vote
1answer
123 views

How do I row reduce a matrix mod 26 when it is singular mod 26?

Cryptography assignment question: matrix $A$ is \begin{equation} A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 ...
2
votes
3answers
65 views

Finding the remainder when $1.1!+2.2!+3.3!+ … +10.10! +2$ is divided by $11!$

Find the remainder when $1.1!+2.2!+3.3!+ ... +10.10! +2$ is divided by $11!$ An attempt: Rearranging: $$\frac{1}{11!}+\frac{2.2!}{11}+\frac{3.3!}{11} \cdots +\frac{10.10!}{11}+\frac{2}{11!}$$ ...
0
votes
1answer
41 views

Combinatorics and Linear Alegbra

$$T = \{1011, 0112, 2101\} \subset Z_3^4$$ Is there any efficient way to find the span for set T other than checking all 27 possibility? If so, how to do it?
1
vote
1answer
67 views

Probabilistic Algorithm for Determining if a Matrix is Nonsingular.

I was reading through Problem-Solving Through Problems and ran into the following problem, Determine whether the following matrix is singular or nonsingular: $$ \begin{bmatrix} 54401 & 5768 ...
3
votes
0answers
476 views

How can I solve system of linear equations over finite fields in WolframAlpha?

Is it possible to solve system of linear equations over finite fields using Wolfram Alpha? If yes, how can I do that? Let us take a system $x+y+z=0$, $2x+y+2z=0$, $x+3y+z=0$. If I want to solve this ...
4
votes
2answers
260 views

Solving a system of equations using modular arithmetic

I am trying to implement a solver for the game lights out. You have a grid of lights, when you click on one of them the light you clicked and its four neighbours change colour, with the light starting ...
0
votes
1answer
82 views

Bases of $\mathbb{F}_p^2$

Let $\mathbb{F}_p$ be a prime field, and let $V=\mathbb{F}_p^2$. Prove: The number of bases of V is equal to the order of the general linear group $GL_2(\mathbb{F}_p)$
8
votes
1answer
90 views

Finding the generators of a subgroup of $\mathrm{SL}_2(\mathbb Z)$

I am trying to solve the following problem: Let $T_{ij}(c)\in\mathrm{SL}_2(\mathbb Z)\ (i\neq j)$ be the elementary matrix which represents the elementary row operation of adding the $j$-th row ...
1
vote
1answer
22 views

generating a vector given other vectors in modulo 11

how to show that vector $X4=\begin{bmatrix}0 \\ 2 \\ 1 \\ 1\end{bmatrix}$ can be generated with $X1=\begin{bmatrix}9 & 1 & 0 & 0\end{bmatrix}$ $X2=\begin{bmatrix}8 & 0 & 1 & ...
1
vote
1answer
92 views

how to interpret theorem about polynomial factorization over modulo ring?

polynomial $X^n+a_1X^{n-1}+...+a_n \in \Bbb Z_2[X]$ doesn't have linear factors $\iff a_n(1+\sum a_i) \neq 0$. How then $f(X)=X+1$ can has no linear factors? Doesn't the condition expands to ...
3
votes
1answer
138 views

Solve a system of linear congruences

I have this system: $$ \begin{align} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n &= b_1 \mod p \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n &= b_2 \mod p \\ \vdots \\ ...
1
vote
1answer
104 views

Matrix inversion help

If $g(n)$ is an integer functions periodic in $a$ And $\phi(a)$ is eulers totient function And $[r_1,r_2,r_3,...r_{\phi(a)}]$ are the postive integers less then $a$ coprime to $a$ With ...
11
votes
5answers
318 views

Why are there$ 736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?

I'm currently trying to introduce myself to cryptography. I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
0
votes
0answers
118 views

Solving systems of linear congruences with rational coefficients

Is there any way to solve for $x$ in a system of linear congruences with rational coefficients in the following form? $$Ax \equiv b\pmod 2, \space where\space A \in \Bbb Q^{n,m}, b \in \Bbb Q^m$$ ...
2
votes
1answer
273 views

System of Linear Equations using Mod

I just want to check that I did a certain problem correctly. This is it: $$a+b=3 \pmod{26}\\2a+b=7 \pmod{26}$$ Solve for $a$ and $b$ Now I setup the augmented matrix: $$\left[ \begin{array}{ccc} 1 ...
0
votes
1answer
91 views

integer transform

Let be $X$ an integer set: $X=\{0,1,2,\ldots,63\}$. Let be $(x,y)$ two elements from $X$ ($(x,y)\in X \times X$). I want to know if exist two transforms $T_1 :X \times X \to X$ and $T_2 :X \times X ...
0
votes
3answers
62 views

elementary congruence statement proof

it is me again :), i am trying to prove this statement of congruence, the statement is as follows: $a \equiv b \mod m \Longrightarrow a^{k} \equiv b^{k} \mod m $ for all $ k \in \mathbb{N}$ i ...
1
vote
2answers
67 views

congruence theorem prove

i am trying to prove this statement of congruence which is not really hard, but i am stumbling across the simple step. statement: $a \equiv b \mod m \land c \equiv d \mod m \Longrightarrow ac ...
1
vote
2answers
364 views

Solving $4$ simultaneous linear equations modulo $26$

I'm trying to solve these equations to solve a ciphertext which is encrypted by the Hill Cipher. I tried to solve these equations algebraically. (First choose two of them and try to eliminate one ...
2
votes
1answer
624 views

Modular Arithmetic over a Matrix

What are the rules for modular arithmetic when multiplying two matrices? I want to calulate $C = AB \mod{n}.$ Aside from the obvious way of performing the modulo after the multiplication, when and ...
6
votes
2answers
510 views

Find all linearly dependent subsets of this set of vectors

I have vectors in such form (1 1 1 0 1 0) (0 0 1 0 0 0) (1 0 0 0 0 0) (0 0 0 1 0 0) (1 1 0 0 1 0) (0 0 1 1 0 0) (1 0 1 1 0 0) I need to find all linear ...
1
vote
1answer
100 views

MOD functions spanning the vector space $\mathbb{R}^{\{0,1\}^n}$

Let $MOD_{a,c}^r:\{0,1\}^n\to\{-1,1\}$ denote the function $$MOD_{a,c}^r(x)=\cases{-1 \ a\cdot x+c\equiv0\ (\text{mod r}) \\ 1 \ \text{else }}$$ Here $\cdot$ is the usual dot product. I want to ...
2
votes
1answer
410 views

Existence of solution of a modular system of linear equations

I want to know if a given system of linear integer equations has an integer solution. I know it is the case if and only if it has a solution modulo $n$ for all integer $n$. What I do not know is when ...
4
votes
1answer
69 views

Calculating with inverses in $\mathbb Z_7$

I want to calculate $\frac{\overline{2}}{\overline{3}}$, $\frac{\overline{1}}{\overline{9}}$, $\frac{\overline{32}}{\overline{9}}$ in $\mathbb{Z}_7$. About first example my book says: ...
2
votes
1answer
174 views

Complexity of Gauss elimination over ring $Z_n.$

Is there some polynomial upper-bound for Gauss elimination over ring $Z_n$? I'm interested in polynomial bound depending from size of matrix and $\log n$. I also have the same question about the ...
2
votes
3answers
1k views

I don't understand why the inverse is this?

my question is related to matrix inverting and Hill cipher(you don't have to know what it is to help me) My teacher gave me an example. First we have a matrix (the key matrix) that multiplied by a ...
1
vote
2answers
1k views

What are the rules for basic algebra when modulo real numbers are involved

That is real numbers modulo an integer. I'm just interested in shuffling around +-*/ operations. If a concrete example helps here's my current problem. (I'm from a programming background so there's ...
1
vote
1answer
397 views

How can I solve a vector equation in Z2?

I have a equation with 256 variables * 256-dimensional vectors in $\mathbb{Z}_2 $: $$ x_1 \cdot \left(\begin{array}{c} 1\\ 1\\ 1\\ \vdots\\ 0 \end{array}\right) + x_2 \cdot ...
2
votes
2answers
1k views

how to solve linear equations involving modulo?

In one of the programming work I am doing, I encountered a set of linear eqns. with modulo. I am putting it in simple format with only 2 variables, $$(a_{11}x + a_{12}y) \mod 8 = b_1$$ $$(a_{21}x + ...