All Questions
6,289 questions
2
votes
1
answer
1k
views
On an eigenvalue inequality
Let $\lambda_1 (\cdot)$ be the larger absolute value
eigenvalue of a $2\times2$ matrix and $\lambda_2 (\cdot)$
the smaller absolute value eigenvalue of a $2\times2$ matrix, i.e.
$|\lambda_1 (\cdot)| \...
- 29
2
votes
1
answer
442
views
FFT based algorithm for special matrices
Contest problems with connections to deeper mathematics
This question is with regard to Elkies' answer to the above post.
Vandermonde determinant can be computed using FFT techniques.
Can Moore ...
- 13.9k
-1
votes
1
answer
809
views
On an eigenvalue inequality [closed]
Let $\lambda_1 (\cdot)$ be the larger absolute value
eigenvalue of a $2\times2$ matrix and $\lambda_2 (\cdot)$
the smaller absolute value eigenvalue of a $2\times2$ matrix, i.e.
$|\lambda_1 (\cdot)| \...
- 29
5
votes
3
answers
3k
views
Spectral properties of the LDL^T matrix factorization
Assume that a square, symmetric matrix $A$ can be factored into $A=LDL^T$ where $L$ is unit lower triangular and $D$ is diagonal. For indefinite $A$, $D$ may have $2x2$ blocks on the diagonal. How ...
- 757
7
votes
6
answers
4k
views
Presentation of the Clifford group by generators and relations?
The Clifford group $\mathcal{C}_n$ is a matrix group on $\mathbb{C}^{2^n}$ generated by tensor products of the following matrices:
$$
P = \begin{pmatrix} 1 & 0 \\\\ 0 & i\end{pmatrix}
\quad
H =...
- 241
3
votes
1
answer
829
views
polynomial matrices and its spectrum
Hello, all!
I have a polynomial non-singular square matrix over $\mathbf{F} _q[x]$,
$$\underset{l \times l}{G(x)} = \left( \begin{matrix} g _{0,0}(x) & g _{0,1}(x) & \ldots & g _{0,l-1}(...
1
vote
1
answer
2k
views
Can one efficiently optimize over the inverse of matrix?
Hello,
I have the following problem:
Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), ...
- 53
11
votes
0
answers
305
views
Generalized Classical Adjoints and Factorizations of the Characteristic Polynomial
This is idle noodling, and I'm prepared to learn that it's foolish as well as idle. But....
Let $M$ be an $n\times n$ matrix over, oh, let's say an algebraically closed field for now. There have ...
- 23k
0
votes
1
answer
655
views
Fuzzy vector similarity
Hi all,
I have two multi-dimensional vectors representing documents $\vec{a}$ and $\vec{b}$.
Considering cases where there is no overlap between $a$ and $b$ ($a \cap b = \emptyset $), traditional ...
- 103
2
votes
1
answer
816
views
The generator polynomial of cyclic code
Let $q$ be a power of prime number $p$ and let $F_{q^2}$ be a finite field of order $q^2$.
Suppose that "-" be a conjugation operation that is defined as follow:
$-:F_{q^2} \longrightarrow F_{q^2}$...
- 632
1
vote
1
answer
3k
views
Convergence of Eigenvalues
Suppose we have a matrix $A_n = \frac{1}{n}\sum_{i=1}^nX_i X_i^T$, where $X_i$ is a $p$-dimensional random-vector. We also know that $E(XX^T) = \Sigma_{p \times p}$. Let us denote the $j$-th largest ...
- 63
3
votes
0
answers
919
views
Linear independence over Q of logarithmic powers of prime numbers
I denote $p_k$ the $k^{th}$ prime number ($p_1=2$, etc...)
Clearly, for any $n\in \mathbb{N}^*$, $(\log p_k)_{1\leq k\leq n}$ is linearly independent over $\mathbb{Q}$.
My question concerns a ...
- 101
3
votes
0
answers
107
views
Linear relations with small coefficients
NOTE: Slightly more general question follows my specific one at the top
For $1 \leq i,j \leq n$, let $e_{ij}$ be the vector in $\mathbb{R}^{n^{2}}$ with a 1 in entry $(n-1)i + j$, and 0's everywhere ...
- 83
5
votes
1
answer
1k
views
Algebra - Decomposition of a matrix polynomial
Dear All,
This is related with a problem that I'm trying to solve on my PhD dissertation in econometrics, and I thought that some mathmatician can know the answer.
What is known about a possible ...
- 51
4
votes
2
answers
982
views
Simultaneous decomposition into generalized eigenvectors
This is my first question here, so please excuse me if it is too elementary.
I was wondering if the notion of a simultaneous decomposition into eigenspaces could be generalized in a special way I ...
- 165
1
vote
2
answers
2k
views
Periodic matrices in SL(3,Z)
Periodic matrices in SL(3,Z) will be conjugated to
product of periodic matrices in SL(2,Z) by +- indentity on a third
integer direction. Is this true?
Sorry, following your comments, maybe ...
- 336
3
votes
0
answers
527
views
3-SAT and a matrix of linear forms representing a non-degenerate matrix
This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question.
As before, let $k$ be a field with $p$ elements. Consider the ...
- 3,897
3
votes
4
answers
4k
views
Fast multiplication of constant symmetric positive-definite matrix and vector.
Consider the matrix $H=H^T$, $H>0$, $H \in R^{n \times n}$, and the vector $v \in R^n$. In a numerical algorithm, I need to compute the product $b = Hv$. Right now I am following the naive approach:...
- 33
4
votes
1
answer
842
views
determining if a matrix of linear forms represents a non-degenerate matrix
Let $k$ be a field with $p$ elements. Consider the following computational problem
Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{...
- 3,897
9
votes
2
answers
954
views
Extremal properties of the determinant for matrices with entries in a fixed subset of $[-1,1]^{n^2}$?
Given a multiset $S\subset [-1,1]^{n^2}$, we set
$$m(S)=\min\vert \det(M)\vert$$
where the minimum is over all matrices with entries forming the multiset $S$
and
$$a(n)=\max m(S)$$
where the maximum ...
- 17.9k
1
vote
0
answers
538
views
Representing vertices of a cube using linear combination of tensor product of smaller cubes
Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.
Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)
...
2
votes
1
answer
453
views
eigen-decomposition of a special companion matrix
I have a special type of companion matrix, where the "special" part is that each element in the matrix are matrices. For instance, the diagonal with "1":s is instead a diagonal with identity matrices, ...
- 23
1
vote
1
answer
1k
views
Characterizing the set of self-orthogonal complex vectors
Let $v\in \mathbb{C}^n$ be an $n$ dimensional complex vector. Define the non-standard bilinear form $\left< u,v \right> = u^T v$ (the usual inner product except without the conjugation). What ...
- 757
0
votes
1
answer
409
views
Need help to find an efficient algorithm for the following problem!
Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$.
Given $A_{n\times n}$ is the covariance matrix of $x$.
$u$ is a given n-dimensional vector of real ...
- 131
0
votes
1
answer
307
views
Comparing iterative methods for linear systems
For a tridiagonal matrix of the from
\begin{bmatrix}
a & -b & \newline
-b & a & -b \newline
& \ddots & \ddots & \ddots \newline
& & & & -...
5
votes
1
answer
637
views
"Orthogonal complement" in $\mathbb{Z}_q^n$
Let $W$ be the finite $\mathbb{Z}$-module obtained from $\mathbb{Z}_q^n$ with addition componentwise where $\mathbb{Z}_q$ is the integers mod $q$. Let $V$ be a submodule of $W$. Let $V^{\perp} = \{w \...
- 53
3
votes
3
answers
3k
views
Generalization of eigenvalues/vectors to modules?
What is the generalization of eigenvalues/vectors to modules?
To be specific, given a "vector" v in a module over some ring, and a linear "operator" O from the module to itself (please feel free to ...
3
votes
0
answers
390
views
Approximate action of unitary matrix with permutation matrix
Given a unitary matrix Q and a symmetric matrix B, I am trying to find a permutation matrix P such that
$ || QBQ^{T} - PBP^{T} ||_{F} $
is minimized.
The straightforward method of minimizing $ ...
1
vote
1
answer
253
views
Chain of ideals in a complex algebra
Suppose $\mathfrak{A}$ is an unital algebra over complex numbers and $\mathfrak{J}$ is chain of left-ideals in $\mathfrak{A}$ ordered by inclusion such that none of its elements is countably generated....
- 31
0
votes
2
answers
256
views
Positivity and symmetrization
Let $A$ be a symmetric positive matrix, and let $B$ be invertible. Is
$$BAB^{-1} + B^{-1}AB$$
always positive?
Let $C$ be a real matrix with real positive spectrum. Is
$$C + C^T$$
positive?
Are ...
- 503
2
votes
2
answers
599
views
Eigenvectors of a diagonalizable matrix
Suppose we have a n-by-n symmetric matrix K which can be factorized in a way, K = H * L * H', where L is a m-by-m diagonal matrix and H is a n-by-m matrix. In addition, let's assume n <= m.
Can we ...
- 21
17
votes
4
answers
2k
views
interlacing roots/eigenvalues results and modern analogues
Is there any relation between these theorems on interlacing roots?
The roots of $f(x), f'(x)$ interlace (if all the roots of $f(x)$ are real and have real coefficients).
The eigenvalues of an $n \...
- 22.8k
0
votes
1
answer
130
views
Maximal length vector under constraints
Consider a criculant symmetric $M$ an $n \times n$ matrix with $0$ and $1$ entries and $r$ entries of $1$ in each row with the diagonal values taken as $1$. I am looking for a $0-1$ vector $v$ with ...
- 800
0
votes
0
answers
429
views
[]-infinity algebra and Projective representation
This is a very vague question.
We know that some algebra structures can be viewed as modules of some fantastic stuff, call T. Such examples include: Abelian groups are $\mathbb{Z}$-modules, chain ...
- 1,271
7
votes
3
answers
3k
views
Algorithm for the smallest (algebraic) eigenvalues of a symmetric (sparse) matrix
Hi,
I'm looking for a way to get the negative eigenspace of a large (sparse) symmetric matrix. This matrix is basically a discretized version of the operator $-\Delta + V$, $V$ negative, on some ...
- 411
27
votes
1
answer
4k
views
If $V$ is a vector space with a basis. $W\subseteq V$ has to have a basis too?
Suppose $V$ is a vector space, we say that $\mathcal B$ is a basis for $V$ if:
Every $v\in V$ can be written as a linear combination of elements of $\mathcal B$;
If $\sum\alpha_i b_i = 0$, where $\...
- 39.8k
15
votes
3
answers
1k
views
The normalizer of $\mathrm{GL}(n,\mathbf Z)$ in $\mathrm{GL}(n,\mathbf Q)$
It seems that the normalizer of $H=\mathrm{GL}(n,\mathbf Z)$ in $G=\mathrm{GL}(n,\mathbf Q)$ is "almost" equal to itself, that is,
$$
N_G(\mathrm{GL}(n,\mathbf Z))=Z(G) \cdot \mathrm{GL}(n,\mathbf Z)
...
- 303
3
votes
1
answer
1k
views
Bounding the von Neumann entropy of a density matrix with the Hilbert-Schmidt norm
Question
Suppose I have a $D$-dimensional density matrix $\rho_0$
$\rho_0^\dagger = \rho_0 \quad, \quad \mathrm{Tr} \rho_0 = 1 \quad, \quad \rho_0 > 0,$
with a known spectrum $\{\lambda_i^0\}$ and ...
- 846
5
votes
3
answers
1k
views
Algorithm for the intersection of a vector subspace with a cone of non-negative vectors
Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
3
votes
2
answers
5k
views
Volume change under linear transformation
It is well-known, that given a linear transformation $f \colon \mathbb R^n \rightarrow \mathbb R^m$, where $m \ge n$, the $m$-dimensional volume of an image of any measurable subset $S \subseteq \...
1
vote
2
answers
313
views
How many DISTINCT vectors we get from pairs v_i + v_j for some set of given vectors v_i ?
Consider some set of vectors v_i i=1...N , v_i \in Z^k.
e.g. N = 10^4; k = 10
Consider all possible sums: v_i + v_j.
Is it possible to estimate how many DISTINCT vectors we get in advance without ...
- 24.9k
10
votes
1
answer
4k
views
Special considerations when using the Woodbury matrix identity numerically
Are there any special considerations when using the Woodbury matrix identity numerically? What is the best metric for numerical stability in this case? Can anyone point me to a good reference?
The ...
- 211
10
votes
1
answer
1k
views
Intrinsic description of the image of $V \to V^{**}$
Let $V$ be a vector space over a field $K$. Call a linear map $F : V^* \to K$ representable if there is some $v \in V$ such that $F(w) = \langle w,v \rangle$ for all $w \in V^*$. Here, $\langle w,v \...
- 63.1k
4
votes
1
answer
1k
views
Solving the matrix equation $XX^t = A$ for binary matrix $X$
How to find all matrices $X \in \{0,1\}^{n \times m}$ that satisfy these equations?
$$X X^t = A \\ \sum_{j=1}^m x_{ij} = 2$$
These articles maybe could help us:
Completely Positive Matrices
Solving ...
- 175
1
vote
3
answers
640
views
Eigenvalues of Krylov matrices
Let an $n\times n$ matrix ${\bf A}$, the all ones vector ${\bf w}$, and the $n\times n$ Krylov matrix
$${\bf K}_n = \left[ {\bf w}\;\;{\bf A}{\bf w}\;\;\ldots \;\; {\bf A}^{n-1}{\bf w}\right].$$
Is ...
- 449
20
votes
3
answers
6k
views
When is $\ker AB = \ker A + \ker B$?
Prove/ Disprove: Let $n$ be a positive integer. Let $A$, $B$ be two $n \times n$ square matrices over the complex numbers. If $AB = BA$ and $\ker A = \ker A^2$ and $\ker B = \ker B^2$
then $\ker AB = ...
- 685
6
votes
6
answers
2k
views
How many 0, 1 solutions would this system of underdetermined linear equations have?
The problem:
I have a system of N linear equations, with K unknowns; and K > N.
Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1.
Here's an example with N=11 ...
- 163
5
votes
1
answer
419
views
positive hermitian elements in $M_n(\mathbb{C})$
Elements of the set $P$ of positive hermitian $n×n$ matrices over complex numbers
have some special properties:
(i) they are closed under sum,
(ii) they are closed under multiplication by positive ...
- 179
8
votes
1
answer
1k
views
Calculating a curvature tensor by polarization
I'm reading some articles by Siu and Nannicini on the Weil-Petersson metric associated to families of compact Kahler-Einstein manifolds. In each article Siu and Nannicini construct a Weil-Petersson ...
- 4,343
2
votes
1
answer
2k
views
How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) ("mathematicalized reformulation")
New edition of the question, "mathematicalized" (thanks to Gerhard).
Consider and integer valued n*n matrix M, with integers elements in the range -N < m < N.
I want to find integer-valued ...
- 24.9k