All Questions
32 questions
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
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
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
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
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
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
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
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
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
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
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
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
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
3
votes
1
answer
77
views
Dimension of fixed vectors of a semi-linear operator
Let $L$ be a field with a field embedding $\sigma:L \rightarrow L$, and $K=L^{\sigma}$ be the fixed field of $\sigma$. For $A \in M_n(L)$ a matrix, consider the set $X=\{x \in L^n|Ax=\sigma(x) \}$ ...
- 6,602
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
1
vote
1
answer
676
views
How to verify the characteristic polynomial? [closed]
I am computing the characteristic polynomial of a matrix over a number field, using the minimal polynomial of it. Is there a fast way to verify the characteristic polynomial of a big matrix ?
- 149
2
votes
1
answer
217
views
Diagonalising a symmetric matrix with polynomial entries
Suppose I have a symmetric $2$ by $2$ matrix $M$ whose $(i,j)$-th entry $F_{i,j}(\mathbf{x})$ belongs to $\mathbb{R}[x_1, \ldots, x_n]$ for each $i,j$. I know that for each $\mathbf{x} \in \mathbb{R}^...
- 3,625
3
votes
0
answers
189
views
Is there a reasonable way to check intersection of these set of vectors?
Given $a,m,n,t\in\Bbb Z$, with $n=m^t$ and $a$ arbitrary, and given $\mathbb{Z}$-linearly independent vectors $v_1,\dots,v_n\in\Bbb Z^n$, and an arbitrary vector $w\in\Bbb Z^n$, such that $$\langle ...
- 13.9k
3
votes
0
answers
419
views
(Expected) Size of smallest singular value of a Vandermonde matrix associated to roots of polynomial
Let $n,H$ two fixed positive integers.
Let $P\in\mathbb{Z}[X]$ a monic integral polynomial of height $H$ and degree $n$ taken uniformly at random (i.e. each of the $n$ free coefficients of $P$ is ...
- 313
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
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
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
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, ...
2
votes
1
answer
567
views
integral basis of orthogonal complement
Suppose there are $r$ linearly independent vectors $v_1,\dots,v_r\in \mathbb{R}^n$, all of them have integer-valued entries and $\|v_i\|_\infty\leq m$ for some integer $m$.
My goal is to find an ...
- 145
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
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
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
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