All Questions
Tagged with matrices nt.number-theory
104 questions
29
votes
12
answers
6k
views
When does 'positive' imply 'sum of squares'?
Does anyone have examples of when an object is positive, then it has (or does not have) a square root? Or more generally, can be written as a sum of squares?
Example. A positive integer does not ...
29
votes
3
answers
3k
views
Perron-Frobenius "inverse eigenvalue problem"
The Perron-Frobenius theorem says that the largest eigenvalue of a positive real matrix (all entries positive) is real. Moreover, that eigenvalue has a positive eigenvector, and it is the only ...
- 2,200
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
23
votes
3
answers
2k
views
On determinants formed by binomial coefficients
Let $q$ be a number. Let us consider the $q^2-1$-th line of the Pascal triangle (i.e. numbers ${{q^2-1} \choose i}$, $i=0,1,...q^2-1$). We have $q^2$ numbers.
Let us form naively a $q \times q$ ...
- 305
21
votes
2
answers
2k
views
Lifting matrices mod 2 to integers.
The following question was motivated by my research.
Consider a $n\times n$ matrix whose elements are $0$'s or $1$'s such that the determinant is odd. The question is: is it possible to assign signs ...
- 4,736
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
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
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
17
votes
2
answers
1k
views
The GCD-matrix: generalizing a result of Smith?
Let $M$ be the $n\times n$ matrix, known as the GCD matrix, of entries $M_{ij}=\gcd(i,j)$. In the paper
H J S Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7:208-...
- 43.2k
16
votes
4
answers
930
views
Integer matrices whose determinant equals their norm
Let $M$ be an $2 \times 2$ matrix, with all entries in $\mathbb{N}$:
$$
M=
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix} \;.
$$
So
$$
\mathrm{det}(M) = a d - b c \; .
$$
The
Euclidean norm
(...
- 151k
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
15
votes
1
answer
603
views
Geometry of numbers for three by three matrices?
While trying to use Minkowski's theorem to calculate the (left) class number of a noncommutative ring, I ran into the following problem:
What is the volume of the largest symmetric convex subset $S$...
- 8,688
15
votes
1
answer
475
views
Determinant of a matrix filled with elements of the Thue–Morse sequence
Let $n$ be a positive integer. Suppose we fill a square matrix $n\times n$ row-by-row with the first $n^2$ elements of the Thue–Morse sequence (with indexes from $0$ to $n^2-1$). Let $\mathcal D_n$ be ...
- 6,819
13
votes
2
answers
697
views
in search of a transformation between determinants
Motivated by this MO question. Consider the two matrices $A_n$ and $B_n$ with entries $\binom{2j}i$ and $\binom{n+1}{2j-i}$, respectively; for $1\leq i, \,j\leq n$.
I can show $\det A_n=\det B_n=2^{\...
- 43.2k
13
votes
3
answers
746
views
Is there a row vector $x$ with integer entries such that no entry of $xM$ is $0 \text{ (mod }p\text{)}$?
Let $p$ be a prime and let $M$ be an $n \times m$ matrix with integer entries such that $M\vec{v} \not\equiv \vec{0} \text{ (mod }p\text{)}$ for any column vector $\vec{v} \neq \vec{0}$ whose entries ...
- 305
13
votes
0
answers
713
views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
- 3,897
12
votes
2
answers
3k
views
Eigenvalues of nonnegative integer matrices
Edit
I realized that the key piece of information that I need is question 1, and so I'd like to rephrase this post:
What are the possible eigenvalues of nonnegative integer matrices?
Any answer to ...
- 3,359
12
votes
1
answer
1k
views
Does the Hasse principle hold for the square root problem on symmetric matrices?
Let $S$ be an $n \times n$ symmetric matrix with rational entries.
It is known that the equation $XX^T=S$ has a solution in $\text{M}_n(\mathbb{Q})$
if and only if it has a solution in $\text{M}_n(\...
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
11
votes
3
answers
1k
views
Congruence subgroups as abstract groups
This is probably well know, and maybe even trivial, but not to me. Consider for concreteness the subgroup
$$
\pm\Gamma_0(3)=\left\{\begin{pmatrix}a & b \\ c & d\end{pmatrix}:\;a,b,c,d\in\...
- 13k
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
11
votes
1
answer
410
views
An "existence contra partition of unity" statement for integer matrices?
While reading a blog post on partitions of unity at the Secret Blogging Seminar the following question came into my mind.
Let $n$ be a positive integer and let $B_1$ and $B_2$ be $n \times n$ ...
- 2,600
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
9
votes
2
answers
875
views
n! divides a product: Part II
This is a follow up on another MO question.
Question. For $n\geq2$, the following is always an integer. Is it not?
$$\frac{(2^n-2)(2^{n-1}-2)\cdots(2^3-2)(2^2-2)}{n!}.$$
- 43.2k
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
9
votes
3
answers
544
views
Product of a Finite Number of Matrices Related to Roots of Unity
Does anyone have an idea how to prove the following identity?
$$
\mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix}
x^{-2j} & -x^{2j+1} \\
1 & 0
\end{pmatrix}\right)=
\begin{cases}
...
- 309
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
9
votes
1
answer
709
views
Automorphisms of a matrix in Smith normal form?
Added: Amritanshu Prasad's answer makes it clear that I am really asking for a description of the group of integer unimodular matrices $P$ such that $D^{-1}PD$ is also integer. These matrices are ...
- 2,150
9
votes
1
answer
553
views
What matrix groups can be embedded in $Sp_4$?
In a joint paper with Yifan Yang we constructed an "exotic" embedding
of $SL_2(\mathbb R)$ in $Sp_4(\mathbb R)$ (in fact, of $PSL_2(\mathbb R)$ in $PSp_4(\mathbb R)$),
namely,
$$
\iota\colon\begin{...
- 13.5k
8
votes
4
answers
7k
views
Positive solutions of linear Diophantine equations
Let $A$ be a non-negative integer $k\times n$-matrix (i.e. each entry is non-negative and integer) with $rank(A) = k < n$. Let $b$ be a $k$-dimensional vector with positive integer entries. ...
- 351
8
votes
1
answer
533
views
What is the minimum $k$ such that $A^k \equiv I$ mod p for invertible matrices?
Let $F$ be a finite field of order $p$, where $p$ is prime. For any $n\times n$ matrix $A$ that is invertible over $F$, then there would appear to exist integers $k$ such that $A^{k} = I$. My question ...
- 183
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
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
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
4
answers
526
views
If the series Σ pᵃ⁽ʷ⁾·xᴵʷᴵ is rational, is Σ a(w)·xᴵʷᴵ also rational (summation over words w in a regular language)?
Let $p$ be a prime number and let $a_i$ be a sequence of natural numbers such that the series $\sum_{i=1}^\infty p^{a_i} x^i$ is rational. A warm-up question:
Question 1. Does it follow that the ...
- 3,897
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
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
6
votes
3
answers
1k
views
"Nearly" Fermat triples: case cubic
Suppose $a^2+b^2-c^2=0$ are formed by a (integral) Pythagorean triple. Then, there are $3\times3$ integer matrices to generate infinitely many more triples. For example, take
$$\begin{bmatrix}-1&2&...
- 43.2k
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
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
6
votes
1
answer
192
views
Monte-Carlo computation of the Smith normal form
Quite some time ago I saw an article where a Monte-Carlo algorithm for computing the Smith normal form of an integer matrix was described. In this article the following problem was posed:
Suppose $P, ...
6
votes
1
answer
309
views
Is this generalization of the Hopf map for quadratic field extensions surjective?
Let $k$ be a field, and let $L$ be a quadratic extension of $k$. Denote by $\sigma$ the non-trivial element of $\operatorname{Gal}(L/k)$. Let $M_2(L)$ be the vector space over $L$ of two-by-two ...
- 5,215
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
6
votes
0
answers
336
views
Legendre's three-square theorem and squared norm of integer matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $E_n$ be the set of integers which are the sum of $n$ squares. Let $F_n$ be the set of integers of the form $\Vert A \Vert^2$ with $A \in M_n(...
6
votes
0
answers
228
views
Lower bound for order of matrix modulo $n$
For a positive integer $n$ and a square matrix $A$ with integral entries, let $\text{ord}(A, n)$ be the smallest positive integer $k$ such that $A^k \equiv \mathbf{1} \bmod n$, if such integer $k$ ...
user40023
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
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
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{...
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
5
votes
0
answers
262
views
p-adic analogue of self-adjoint operator
Consider the very well-known result that any Hermitian matrix over $\mathbb{C}$, say $T$, admits a decomposition $T = UDU^*$ where $U$ is unitary and $D$ is diagonal with real entries. I am looking ...
