All Questions
3,680 questions
0
votes
0
answers
31
views
Coxeter Matrix of Dyck Path
I am trying to understand Gjergji Zaimi's answer in What are the periodic Dyck paths?. In the third paragraph he claims that
Next, we define the matrix $X_D$
similarly to the Cartan matrix except we ...
1
vote
0
answers
28
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
4
votes
0
answers
97
views
Dimension of the intersection of the commuting variety with a particular subspace
Let $\mathcal C$ denote the commuting variety of pairs of matrices in $M_n(\mathbb{C})$, defined as:
$$
\mathcal C = \{ (A, B) \in M_n(\mathbb{C})^2 \mid [A, B] = 0 \}.
$$
It is well known that $\...
- 309
7
votes
1
answer
486
views
Invertibility of a matrix defined using inner product
Let $n,m \geq 1$. We fix $n$ distinct vectors $x_1, ... , x_n \in \mathbb{R}^m$. We define $A \in \mathbb{R}^{n\times n}$ as
\begin{equation}
A_{ij} = x_i^T \left(n x_j - \sum_{1 \leq k \leq n} x_k \...
- 2,306
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
2
votes
0
answers
100
views
An inequality related to Problem 10210 AMM 1992 No. 3
Problem. Let $A$ be a $N \times N$ real matrix whose $(i,j)$ entry is $a_{ij} \ge 0, \forall i, j$. Let $1$ denote $N\times 1$ all-ones vector. Prove that
$$N^2 1^\top A^\top A A^\top 1 \ge (1^\top A ...
- 1,053
0
votes
0
answers
46
views
max eigenvalue and schatten-1 norm of depolarizing channel acting on trace-0 Hermitian matrix
Denote $\mathcal{H}^n$ as the $n-$dimension Hermitian matrices. Depolarizing channel $\Delta_p:\mathcal{H}^2\to\mathcal{H}^2$ is defined as $\Delta_p(A)=p\text{ tr }(A)~I/2+(1-p)A$ where $A\in \...
- 91
4
votes
1
answer
90
views
Tight upper bound on a ratio involving symmetric PSD matrices and Kronecker products
Let $\mathbf{A}_i \in \mathbb{R}^{d \times d}$ ($i = 1, \dots, T$) be symmetric positive semidefinite (PSD) matrices. Define the quantity
$$
m = \frac{\lambda_{\max}\left(\sum_{i=1}^T \mathbf{A}_i^2\...
- 73
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
4
votes
1
answer
171
views
Maximizing trace subject to two equality constraints
I am looking at the following optimization problem
$$\begin{align}
\underset{{\bf X}}{\text{maximize}} \qquad&\mathrm{tr}({\bf AX})\\
\text{subject to} \qquad& \mathrm{tr}({\bf X}) = 1,\\
&...
- 43
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
0
votes
0
answers
87
views
Is there a name for "applying linear operations to vector sequences from the right"?
Let $v_1,...,v_n\in\Bbb R^d$ be a sequence of vectors. When we say that we "linearly transform" this sequence, we mean that we apply a linear transformation $T\in\Bbb R^{d\times d}$ to each ...
- 13.6k
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
10
votes
2
answers
455
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
-1
votes
0
answers
21
views
Choosing between matrix normal and multivariate normal for Bayesian inference
I’m working on a Bayesian inference problem where I need to estimate a graph structure G with a spike-and-slab prior on each edge of G. My likelihood model is built on observed data R and covariance ...
- 1
1
vote
1
answer
109
views
Orbit spaces of n-tuples of square matrices under simultaneous conjugation
Let $n, p, \geq 1$ be integers. Denote the set of ordered partitions of $p$ by $\Pi$: each $\pi \in \Pi$ is an ordered $k$-tuple $(p_1,p_2, \dotsc, p_k)$ where $p_1+\dotsb+p_k = p$. Write $\pi \leq \...
- 185
0
votes
0
answers
57
views
Class of covariance matrices invariant under permutations
I am reading a paper on covariance matrix estimation, and in this paper is introduced a class of covariance matrices:
\begin{equation}
U(q, c_0(p),M)=\{\Sigma: \sigma_{ii}\leq M,\quad \max_j\sum_{j=1}^...
- 1
5
votes
1
answer
539
views
Under what circumstances Is a symmetric matrix representable as a Coulomb matrix?
Question:
I am exploring a neural network architecture inspired by physical interactions, where each neuron has associated "mass" and "position" vectors. The weight matrix between ...
- 3,054
1
vote
0
answers
54
views
How computationally efficient are kernel tricks? [closed]
"If we compare to non-kernel polynomial regression it is O(Tnp) where is p is dimension of polynomial while kernel polynomial is O(n^2d) + O(T*n^2) where d is original number of attributes, ...
2
votes
0
answers
67
views
Preserving invertibility with adding rows
Suppose I have two $m\times n$ matrices $A$ and $B$ such that an $m\times m$ submatrix of $A$ is invertible if and only if the corresponding $m \times m$ submatrix of $B$ is. Now let's say I append a ...
- 21
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
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
1
vote
2
answers
86
views
Entrywise $\infty$-norm of squared difference of square roots of matrices
For a positive $n \times n$ definite real matrix $M$ we denote by $\sqrt{M}$ the positive square root of $M$. For an $n \times n$ matrix $A$ denote its entrywise infinity norm by
$$\|A\|_{\infty,\...
- 177
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
15
votes
1
answer
518
views
Pairs of matrices for which traces of powers are independent of the order
Let $A,B$ be $n\times n$ matrices over ${\mathbb C}$ such that, for all $m,k$ and all partitions $(i_1,\ldots ,i_r)$ of $m$ and $(j_1,\ldots ,j_r)$ of $k$ (perhaps with some zero parts),
$${\rm tr}\, (...
- 1,336
0
votes
0
answers
50
views
Degree of determinant of a (non-monic) matrix polynomial
Let $n=2, 3, \dots$ and consider the matrix polynomial $L(\lambda)=\sum_{k=0}^{\ell}A_k\lambda^k$, where $A_k \in \mathbb{C}^{n\times n}$.
In the so-called monic case (or that can be made monic by ...
- 11
2
votes
0
answers
35
views
Limiting spectral distribution of a random matrix with specific structure
First, consider an $N \times N$ Hermitian random matrix $V$ from the Gaussian Unitary Ensemble (GUE). It is well known that the empirical spectral distribution of the GUE satisfies the semicircle law ...
- 21
8
votes
1
answer
361
views
Invertible matrix with group ring coefficient
Before asking the question I do need
some notations.
$G$ a (torsion-free) group, $\mathbb{Z}^{´}=\mathbb{Z}[\frac{1}{2}]$
$R:= \mathbb{Z}[G]$, $R^{´}=\mathbb{Z}^{´}[G]$ group rings.
$Mat_{n}(R)$ the ...
- 223
0
votes
1
answer
102
views
Minimally change matrix with determinant 0
In the following matrix equation, all coefficients $a_{ij}>0$ and all $a_i>0$ and the column sums in the matrix $A$ are all 0
(e.g. $-a_{11}+a_{21}+a_{31}=0$, etc.).
This means that
the ...
1
vote
0
answers
43
views
Inner product on a symmetric sum of tensor products
I have a space $V$ of $6 \times 6$ matrices whose basis is $\{1,S,M\}$; writing the components indices: $\{1_{ij},S_{ij},M_{ij}\}$ where $i,j=1,\cdots, 6$. The inner product on this space is
\begin{...
3
votes
1
answer
234
views
Is there a matrix that has the completely opposite effect of a Hadamard matrix?
First, let me provide some background on the problem:
In the field of Large Language Model quantization/compressions, outliers (abs of outliers are much larger than the mean of abs of all elements in ...
- 31
0
votes
1
answer
118
views
Configurations of signs in a matrix under certain conditions
I have a combinatorial question which is out of my research area.
Given a $2^k\times 2^k$ matrix $A=[a_{i,j}]$ with entries in $\lbrace0,\pm1\rbrace$, where $k$ is a positive integer. Is it possible ...
- 619
2
votes
1
answer
158
views
The relationship between a matrix and its coefficient matrix decomposed in Pauli matrix
For a dimension-$4$ Hermitian matrix $A$, denote pauli matrices $\{I,X,Y,Z\}$ as $\{\sigma_0,\sigma_1,\sigma_2,\sigma_3\}$ respectively. The pauli matrices form a basis of the matrix space if we take ...
- 91
1
vote
1
answer
122
views
distance in the matrix algebra w.r.t. the nuclear norm
Let $\varphi\in\mathcal{M}_n(\mathbb{C})$ and let $Z:=\mathbb{C}\cdot I=\{zI\colon\,z\in\mathbb{C}\}$ be the one-dimensional subspace spanned by the identity matrix $I$. Let moreover $\|\cdot\|_{\...
- 375
0
votes
1
answer
127
views
Under what conditions does $x^TA^{-1}y> 0$ hold? $A$ is a symmetric positive definite matrix,$A\in \mathbb{R}^{n\times n}_+, x,y\in \mathbb{R}^{n}_+$
This is a tricky problem I encountered in my research. $A\in \mathbb{R}^{n\times n}_+, x,y\in \mathbb{R}^{n}_+$, i.e. $\forall 1\leq i \leq n, 1 \leq j\leq n, A(i, j)>0, x(i), y(i)>0$.
As known, ...
- 27
0
votes
0
answers
68
views
Inequality between product of companion matrices and power of Pisot number
Let $d\geqslant 2$ be an integer and consider a convergent sequence of "companion" matrices
$$A_k := \begin{pmatrix}
a_{k,1} & a_{k,2} & \cdots & a_{k,d} \\\
& ...
- 101
2
votes
0
answers
71
views
Are the ranks of the following matrices given by these simple expressions?
The question itself is formulated in the title, so below I specify the matrices and expressions mentioned there. In case if this is something known or can be easily deduced from something known, this ...
- 321
0
votes
0
answers
23
views
Existence of a subregular element with abelian centralizer in a quadratic Lie algebra
All Lie algebras here will be finite dimensionnal complex Lie algebra.
We say that such an Lie algebra $\mathfrak{g}$ is quadratic if there exist a skew-symetric, non-degenerate bilinear form or ...
- 188
1
vote
0
answers
43
views
Catalog of integral symmetric matrices
Let $g$ be an integral symmetric matrix (perhaps with even diagonal components), and define an equivalence relation $g\sim g'$ if $g=Ug'U^T$ with $U$ a unimodular integral matrix.
For fixed $\det g$ (...
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
3
votes
1
answer
187
views
Eigenvalues of certain matrices
We write $R(\theta)=\left(\begin{smallmatrix}\cos(2\pi\theta)&\sin(2\pi\theta)\\ -\sin(2\pi\theta)&\cos(2\pi\theta)\end{smallmatrix}\right)$ for any $\theta\in\mathbb R$.
Let $d,m,n,r$ be a ...
- 2,446
1
vote
1
answer
52
views
Eigendecomposition of a Gram matrix with specified columns
I originally posted this question on Math SE, but I am starting to think it is more suitable to post it here. After waiting about two weeks, I didn't get any activity. The original question is linked ...
- 111
2
votes
0
answers
68
views
Nonlinear random matrix equations
Let $C$ be a matrix; $v$ be a column vector;
$P$, $\Delta$ are random matrices;
$x$ is a random column vector.
$$Cvv^T - \mathbb{E}[P^Tx]v^T - \mathbb{E}[P^Tx v^T \Delta] + O(\Delta^2)= 0$$
$$C^TCv - ...
- 21
0
votes
0
answers
52
views
What are the injective embeddings of R^d into the cone of (semi-) positive definite matrices of dimension d?
How can we characterize the set of all injective functions from $\mathbb{R}^d$ to the set of all symmetric positive definite matrices of dimension d?
- 109
1
vote
0
answers
63
views
The rank of a matrix expression
I'm studying discrete-time LTI systems and state estimators for them. Recently, I studied this paper. I am facing a matrix rank calculation problem and having trouble solving it. I will provide more ...
- 4,484
0
votes
0
answers
53
views
Relations between the optimal solutions of two related SDPs
In system theory, we often encounter Semi-Definite Programs (SDPs) with Linear Matrix Inequality (LMI) constraints, such as those presented in this paper. I have introduced new variables based on the ...
- 4,484
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
4
votes
1
answer
230
views
$\omega\times\omega$-Hadamard matrices
In the following, we define infinite Hadamard matrices.
Let $\omega$ be the set of non-negative integers. If $f,g:\omega\to\{-1,1\}$ are maps, then we say $f,g$ are approximately orthogonal if $$\...
- 48.8k
4
votes
1
answer
421
views
Visualizing the elements of a finite group and does the Gram matrix determine the finite group?
Let $G$ be a finite group with $n = |G|$ elements. By Cayley's theorem for finite groups, we have an injective homomorphism of groups:
$$
\pi : G \rightarrow S_n, \quad g \mapsto \pi(g)
$$
where ...
- 3,054
7
votes
1
answer
118
views
Bound on when sequence of norms of matrix powers starts to decrease
If a matrix $A$ has spectral radius $\rho(A)<1$, it is well-known that $A^n\to0$ as $n\to\infty$, or equivalently $\lVert A^n\rVert\to 0$ for some matrix norm $\lVert\cdot\rVert$; however, it may ...
