All Questions
Tagged with matrices nt.number-theory
104 questions
4
votes
0
answers
167
views
How to prove the following equation (which involves binomials and determinant of 2×2 matrices)?
I have tried many ways to prove the following equation, such as the method of induction and expanding all the terms in the summation,but things got more complicated.I could not find an appropriate ...
- 41
10
votes
2
answers
454
views
Is the number of similarity classes of integer matrices with given minimal and characteristic polynomial finite?
Latimer and MacDuffee proved that there is a bijection between similarity classes of integer matrices with irreducible characteristic polynomial $\chi$ and the ideal class monoid of $\mathbb{Z}[\alpha]...
- 123
2
votes
0
answers
113
views
Numbers of positive terms in polynomials equal A069999
Let $a(n)$ be A069999 (i.e., number of possible dimensions for commutators of $n \times n$ matrices; it is independent of the field). OEIS states that no generating function is known.
Let $P(n,k)$ be ...
- 4,928
5
votes
1
answer
303
views
Efficiently computing $\prod_{i=1}^{n} A_i$
Let $k$ be a nonnegative integer, how to compute $\prod\limits_{i=1}^{n} A_i$ quickly and accurately, where $$A_i=\begin{bmatrix}
0 & 1\\
i^k & 1
\end{bmatrix}?$$
I know if $k=0$, we can use ...
- 696
1
vote
0
answers
121
views
Simple algorithm for A107670
Let $T(n, k)$ be A107670 (i.e., matrix square of triangle A107667). Here we define the triangular matrix $P$ by $P(n, k) = \frac{(n+1)^{2(n-k)}}{(n-k)!}$ for $0 \leqslant k \leqslant n$ and the ...
- 4,928
9
votes
2
answers
794
views
Why do these finite group Dedekind matrices seem to have integer spectrum when specialized to the order of group elements?
Let $p$ be a prime and let $f_p$ be the permutation on the set $\{1,2,\cdots,p-1\}$ which is given by taking inverses in $\mathbb{Z}/(p)$:
$$x \bmod(p) \mapsto \frac{1}{x} \bmod (p)$$
So for instance, ...
- 3,054
1
vote
0
answers
134
views
Number of ways to place 4 kings on nxn chessboard
I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:
In the case where the $4$...
- 47
0
votes
0
answers
33
views
determinantal ideal of sum of Galois conjugate matrices
Given $n$ matrices $A_i \in \mathbb{Z}^{m\times m}$. I am interested in the ideal $I_d(A)$ generated by the $d\times d$-minors of $A = \sum_{i=1}^n x_iA_i \in \mathbb{Z}[x_1, \dots , x_n]$.
The matrix ...
- 61
4
votes
1
answer
278
views
Fibonacci and matrix modular exponentiation
I'm interested in a few problems that are related enough that I decided to put them all in one question.
What are the fastest known algorithms for finding large Fibonacci numbers modulo $p^k$, and ...
- 541
0
votes
2
answers
252
views
“Smallest” non-zero linear combination of vectors to obtain a non-negative vector
We say that a vector $\mathbf{x}$ in $\mathbb{Z}^j$ is non-negative if it is of the form
\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
x_j \\
\end{bmatrix}
where $x_{i} \geq 0$ for all $i=1,\...
- 227
6
votes
0
answers
199
views
Zero-one pairings between sets of vectors
Let
$A\subseteq V$ and
$B\subseteq V^\star$
be spanning sets in
a finite-dimensional real vector space $V$ and
its dual $V^\star$.
Suppose that
$$
\langle b,a\rangle\in\lbrace0,1\rbrace
$$
for all
$a\...
- 809
9
votes
2
answers
646
views
Are these two methods for constructing Hadamard matrices known?
These two observations came while researching the empty set of odd perfect numbers and unitary perfect numbers:
Context:
Let $n$ be a natural number and $D_n$ be the set of divisors.
We can make this ...
- 3,054
2
votes
1
answer
226
views
Inductive Cholesky decomposition to prove that a function is positive definite over the natural numbers?
I am trying to prove that the function:
$$k(a,b):=\frac{1}{\operatorname{rad}\left ( \frac{ab}{\gcd(a,b)^2} \right )}$$
is a positive definite function over the natural numbers. What has sometimes ...
- 3,054
0
votes
1
answer
744
views
A RKHS interpretation of the Rydberg formula for hydrogen and an application for physics?
I was thinking if it is possible to define an inner product between two small physical objects with a positive definite kernel and was led to look at the Rydberg formula:
The Rydberg formula for ...
- 3,054
0
votes
1
answer
171
views
Prime index subgroups of $\langle Q^{i}(\mathbb Z^{2}) \mid i \in \mathbb Z \rangle$ that is invariant under matrix $Q$
Let $Q $ be a matrix in $ \operatorname{GL}(2, \mathbb{Q}) $ and consider the group
$G = \langle Q^{i}(\mathbb Z^{2}) \mid i \in \mathbb Z \rangle := \langle Q^{i}(v) \mid i \in \mathbb Z, v \in \...
- 823
4
votes
1
answer
214
views
Diameter of the unimodular group with Gauss moves
$\DeclareMathOperator\GL{GL}$Consider the unimodular group $\GL_n(\mathbb{Z})$, consisting of integral matrices $A \in \mathbb{Z}^{n \times n}$ such that that $\det(A) =\pm 1$.
It is well known that ...
- 327
1
vote
1
answer
252
views
Smith normal form and last invariant factor of certain matrices
I've copied over this question from what I asked on Mathematics Stack Exchange, in the hope that some experts can provide some relevant insight.
Suppose we have row vectors $x_1$, $x_2$ , $y_1$ , $y_2 ...
- 823
7
votes
1
answer
792
views
Remarkable recursions for the A204262
Let $a(n)$ be A204262 i.e. permanent of the matrix $n\times n$ with elements $\min(i,j)$.
Let
$$
f_{n,\ell}(x)=g_{n,\ell}(x)+f_{n,\ell-1}(\ell)-g_{n,\ell}(\ell), \\
g_{n,\ell}(x)=\int (n-\ell)^2 f_{n-...
- 4,928
18
votes
2
answers
488
views
Encoding primes via ranks of sign matrices
(Reposted from math.SE)
Recently I came across a very simply defined family of matrices: for $n \in \mathbb{N}$, set $A_n := (a_{ij})_{0 \le i, j \le n-1}$, where
$$\displaystyle a_{ij} := (-1)^{\big\...
- 281
4
votes
1
answer
266
views
Positive system of algebraic integers
Let $\mathbb{A}$ be the ring of algebraic integers. Consider a sequence $(d_i)_{i \in I}$, with $I$ a finite set and $d_i \in \mathbb{A} \cap \mathbb{R}_{\ge 1}$, such that $$d_i d_j = \sum_{k \in I} ...
1
vote
1
answer
296
views
A query about modular arithmetic on a matrix
Given a matrix $M$ that consists of a set of $4K$ binary row vectors (each vector entry is 0 or 1) each of length $K$. Moreover, it is known/promised that no subset of rows in matrix add to an all 1 ...
- 13
3
votes
0
answers
163
views
On a decomposition of $2\times2$ integer matrix
Given an integer matrix $\begin{bmatrix}a&b\\c&d\end{bmatrix}$ with determinant $det$ and two positive integers $m,n:m+n=det$, when is it possible to write it sum of two integer matrices $\...
- 13.9k
3
votes
1
answer
135
views
$3\times 3$ magic squares consisting of entries of a dense set $D\subseteq \mathbb{N}$
Starting point. The struggle for a magic square consisting of distinct square numbers is still ongoing, but it has produced an amusing landmark result called the Parker square. One of the issues is ...
- 48.8k
1
vote
1
answer
230
views
Symmetric Integral Matrices
Let $SM_n(R)$ be the set of $n\times n$ symmetric matrices with entries in a ring $R$ and let $A\sim B$ for such matrices if $A=C^T\cdot B\cdot C$ for some $C\in SL(n,R).$ It is an equivalence ...
- 2,390
4
votes
2
answers
574
views
Existence of solution for a system of quadratic diophantine equations / symmetric quadratic froms
I am interested in solving, or even just deciding the existence of a solution, for a system of quadratic diophantine equations.
Let $p$ be a prime congruent to 1 modulo 8, so $ p =17$ is the first ...
- 91
15
votes
2
answers
1k
views
Vanishing of a sum of roots of unity
In my answer to this question, there appears the following sub-question about a sum of roots of unity. Denoting $z=\exp\frac{i\pi}N$ (so that $z^N=-1$), can the quantity
$$\sum_{k=0}^{N-1}z^{2k^2+k}$$
...
- 52.3k
-1
votes
1
answer
186
views
Public key cryptography based on non-invertible matrices, part II
Closely related to this question
and extending comment
of R. van Dobben de Bruyn.
Working over $\mathbb{F}_p$ and all matrices of square $n \times n$.
Alice chooses invertible $X_A$ and non-...
- 25.4k
6
votes
1
answer
566
views
Public key cryptography based on non-invertible matrices?
Added Wed 13 Apr 2022
I have written a short note with experimental data,
which shows not all pseudo keys are good keys.
Public key cryptography based on non-invertible matrices
We got public key ...
- 25.4k
5
votes
1
answer
254
views
Convergence of a series related to $\mathrm{SL}_2({\mathbb N})$
The question The number $\pi$ and summation by $SL(2,\mathbb Z)$ considers the series
$$\sum(\lVert x\rVert+\lVert y\rVert-\lVert x+y\rVert)$$
where the series runs over vectors $x,y\in{\mathbb N}^2$ ...
- 52.3k
6
votes
1
answer
392
views
Arithmetic properties of positively reduced $2\times 2$-matrices
Call a $2\times 2$ matrix with coefficients in $\{0,1,2,3,\ldots\}$
positively reduced if any row or column reduction (given by replacing a row/column by itself minus the other row/column) produces
at ...
- 17.9k
3
votes
1
answer
308
views
Tangent numbers, secant numbers and permanent of matrices
Inspired by Question 402572, I consider the permanent of matrices
$$f(n)=\mathrm{per}(A)=\mathrm{per}\left[\operatorname{sgn} \left(\sin\pi\frac{j+2k}{n+1} \right)\right]_{1\le j,k\le n},$$
where $n$ ...
- 884
20
votes
2
answers
1k
views
Euler numbers and permanent of matrices
Motivated by Question 402249 of Zhi-Wei Sun, I consider the permanent of matrices
$$e(n)=\mathrm{per}\left[\operatorname{sgn} \left(\tan\pi\frac{j+k}n \right)\right]_{1\le j,k\le n-1},$$
where $n$ is ...
- 884
8
votes
0
answers
392
views
Bounding eigenvalues by taking high powers of matrices: history?
Let $A$ be real symmetric matrix. It is a well-known observation that we can bound any eigenvalue $\lambda$ of $A$ by using the fact that
$$\lambda^{2 k} \leq \textrm{Tr} A^{2 k}$$
for any $k\geq 1$. ...
- 20.2k
3
votes
1
answer
457
views
On $\frac{(-1)^{(n-1)/2}}n\mathrm{per}\left[\tan\pi\frac{j+k}n\right]_{1\le j,k\le n-1}$ with $n\in\{3,5,7,\ldots\}$
Recall that the permanent of a matrix $A=[a_{j,k}]_{1\le j,k\le n}$ is given by
$$\mathrm{per}(A)=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$
Let $n$ be an odd integer greater than one. In 2019 I ...
- 15.6k
2
votes
0
answers
137
views
Reference for $2$-by-$2$ integer matrices
Currently I am studying number theory, in particular modular functions and imaginary quadratic fields. I am looking for a reference on $2$-by-$2$ integer (or rational) matrices, especially:
...
- 2,375
5
votes
0
answers
152
views
Distance function on generalized upper half planes
Let $\mathbb{H}^n$ be the quotient $GL_n(\mathbb{R})/O(n) \cdot \mathbb{R}^\times$, which at least in the theory of automorphic forms is called a generalized upper half plane. We could also think of $...
- 767
0
votes
1
answer
120
views
Complexity of solving linear equations plus disequality constraints $a \ne b$
Let $K$ be ring and $S$ linear homogeneous system with $n$ variables $x_i$ over $K$.
Add to $K$ linear disequalities of the form $x_k \ne x_l$
and let the final system be $S'$. If $K=\mathbb{F}_2$,
$...
- 25.4k
5
votes
1
answer
235
views
Can a product of Cohn matrices over the Eisenstein integers with non-zero, non-unit coefficients be a Cohn matrix?
For $k > 1$, is it possible that $\begin{pmatrix} a_1 & 1 \\ -1 & 0 \end{pmatrix}\begin{pmatrix} a_2 & 1 \\ -1 & 0 \end{pmatrix}\ldots \begin{pmatrix} a_k & 1 \\ -1 & 0 \end{...
11
votes
3
answers
591
views
Non-singular matrix with restricted entries
Given a set $S$ of integers with $1 \not\in S$, let us consider the set $\mathcal{M}$ of all the symmetric matrices $M$, such that:
All the diagonal entries of $M$ are equal to $1$.
All the off-...
- 571
26
votes
5
answers
1k
views
Condition for a matrix to be a perfect power of an integer matrix
I have a question that seems to be rather simple but for I got no clue so far.
Let's say I have a matrix $A$ of size $2\times 2$ and integer entries. I want to know if there is a kind of test or ...
- 1,889
2
votes
1
answer
110
views
Zero entries in matrix powers over finite rings
Let $R$ be the finite ring of the integers modulo $q$ or $GF(2^k)$.
Let $M$ be $n \times n$ matrix with entries from $R$.
Assume $N,I,J$ are integers and for $ 1 \le i \le N-1$ we have $M^i[I,J]=0$
...
- 25.4k
4
votes
1
answer
220
views
Sum of divisors and unitary divisors as the eigenvalue and the spectral norm of some addition matrix?
Let $n$ be a natural number and $D_n$ be the set of divisors.
We can make this set to a ring by observing that each divisor $d$ has
$$0 \le v_p(d) \le v_p(n)$$
Hence we can add two divisors $d,e$ by ...
user6671
21
votes
1
answer
653
views
Characteristic polynomial of the Gcd matrix
Let $A_n$ be the $n \times n$-matrix with entries $\gcd(i,j)$ and $f_n$ the characteristic polynomial of $A_n$.
Question: Is $f_n$ irreducible over $\mathbb{Q}$ for all $n$ except $n=8$?
This is ...
- 26.5k
0
votes
1
answer
346
views
Sum elements in two dimensional arithmetic progression
I have two matrices,
$$A= \left[ \begin{matrix} 5 & 10 & 15 & \cdots \\ 17 & 28 & 39 & \cdots \\ 35 & 52 & 69 & \cdots \\ \vdots & \vdots & \vdots & ...
- 41
7
votes
0
answers
905
views
The Möbius function as eigenvalues
Let the $N$ by $N$ matrix $A$ be defined by the tetration:
$$\Large \text{If } \gcd(n, k)=1 \text{ then } A(n,k)= \underbrace{e^{e^{\cdot^{\cdot^{e^{\Re\left(\frac{1}{n^s}\right)}}}}}}_m \text{ else }...
- 1,183
7
votes
1
answer
502
views
Do the following binary vectors span $\mathbb{R}^n$?
Defining the binary vectors
Let an ordered triple of natural numbers $(r, d, n)$ such that $0 \leq r < d \leq n$ be given.
Consider the binary vector $v_{(r,d,n)} \in \mathbb{R}^n$ such that for ...
- 123
7
votes
0
answers
177
views
Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?
Let $A$ be a $2n$-by-$2n$ matrix with entries in
$\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal
matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$
has rank $\...
- 20.2k
11
votes
3
answers
605
views
Number of matrices with bounded products of rows and columns
Fix an integer $d \geq 2$ and for every real number $x$ let $M_d(x)$ be number of $d \times d$ matrices $(a_{ij})$ satisfying: every $a_{ij}$ is a positive integer, the product of every row does not ...
- 213
3
votes
1
answer
149
views
Analogue of Perron numbers for non-negative matrices
If $A$ is a square matrix with positive integer coefficients with a biggest real eigenvalues $\lambda>1$, then $\lambda$ is a Perron-number, which means that it is a real algebraic integer bigger ...
- 7,722
3
votes
0
answers
77
views
How can I find the integral orthogonal group of a given symmetric positive definite form?
I wonder how one can study the integral orthogonal group of a given (symmetric, positive definite) bilinear form like the one described by the following matrix:
$$M=\begin{bmatrix}
x_1 &...
- 362