# Tagged Questions

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 ...
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$?
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 ...
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 ...
20 views

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 ...
123 views

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

Cryptography assignment question: matrix $A$ is A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 ...
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!}$$ ...
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?
67 views

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 ...
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 ...
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$$ ...
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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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: ... 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 ... 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 ... 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 ... 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 ...
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 + ...