All Questions
921 questions with no upvoted or accepted answers
0
votes
0
answers
113
views
Error bounds on the expansion of square root of matrix
I'm working on a problem and was lead to trying to find an approximation for the square root of a matrix. I came across a way of doing this using holomorphic functional calculus. However, my first ...
- 427
0
votes
0
answers
108
views
Solutions to matrix equations in the non-negative integers
For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers.
I've been doing this with Sage's mixed integer ...
- 101
0
votes
0
answers
79
views
Eigendecomposition of $A=I+BDB^H$
Suppose that we have $$A = I_m + BDB^H$$ where matrix $A$ is $m \times m$, matrix $B$ is $m \times k$, $BB^H \neq I_m$ and $D$ is a $k \times k$ diagonal matrix. Can we obtain the eigendecomposition ...
- 13
0
votes
0
answers
61
views
Combining quadratic and linear matrix terms into a quadratic term
Given
$$ C = AFA^T + A\bar{F} $$
where $A = [A_1 A_2]$, $F = \begin{bmatrix}
F_1 & F_2 \\
F_2^T & F_3
\end{bmatrix}$, $\bar{F} = 2 \begin{bmatrix}
\bar{F}_1 \\
\bar{F}_2
\end{bmatrix}$ such ...
- 1
0
votes
0
answers
236
views
Eigenvectors of a matrix
Let $M$ be a square matrix of order $n\times d$. Let $\xi_{1},\dots,\xi_{n\times d}$ be an orthonormal basis of $\mathbb{R}^{n\times d}$ formed of eigenvectors of $M$. We have
$$\xi_{i}=(\lambda_1, 0,...
0
votes
0
answers
54
views
Is there a method to find a vector that optimizes a Rayleigh quotient over a subspace?
Let $M\in\mathbb{C}^{n\times n}$ be an arbitary Hermitian matrix and let $E$ be a subspace of $\mathbb{C}^n$.
Is there a method to find vectors $y,z\in E$ such that
$$\dfrac{y^*My}{y^*y}=\sup_{x\in E\\...
- 596
0
votes
0
answers
30
views
Signs of difference matrices (sum of submatrices)
Given matrix $A \in \mathbb{R}^{m \times n}$, are there any results related to its difference array
$$A^* \triangleq \left[sign(a_{i,j} + a_{r, s} - a_{r, j} - a_{i, s})\right]_{i<r, j<s}?$$
Or ...
- 75
0
votes
0
answers
45
views
On full rank submatrices of a construction
Take two matrices $T_1$ and $T_2$ in $\mathbb Z^{n\times n}$ with entries uniformly in $[-b,b]\cap\mathbb Z$ at some $b>0$. The matrices will be of rank $n$ each with probability at least $1-\frac1{...
- 1,826
0
votes
0
answers
47
views
"Probability" for a partitioned matrix to be singular
Let $A,B\in\mathbb{R}^{n\times n}$ be two nonsingular matrices with $A\ne B$, and consider the following partitioned matrix
$$
M:=\begin{bmatrix}AA^\top + BB^\top & A^\top \Delta_1 A + B^\top \...
- 2,712
0
votes
0
answers
101
views
Find occurrences of certain matrix inside a matrix
This problem occurred from my need to find all graphs with a certain topology inside a bigger one. I don't need the subgraphs but the graphs that have the exact topology I am searching.
We know for ...
- 101
0
votes
0
answers
50
views
Generalized eigenvectors product
Let's consider a real square matrix $A$ with eigenvalues $\lambda_n$ and eigenvectors $\mathbb x_n$, i.e. $A \mathbb x_n = \lambda_n \mathbb x_n$.
Suppose there are some generalized eigenvectors $\...
- 141
0
votes
0
answers
59
views
A system of inequalities involving a skew-symmetric integer matrix
Which skew-symmetric integer matrices $S$ satisfy the following inequalities
$SV_i \ne z_iE_i$ for all $i = 1,\cdots, n$
where
$V_i$ denotes the column with integer entries such that the $i$-th ...
- 356
0
votes
0
answers
41
views
Orthogonality condition of symmetric matrix pencil
Let $P(\lambda)=\lambda M−L\in \mathbb{R}^{n \times n}$ be a matrix pencil with symmetric nonsingular matrix $M$ and $L$ is a weighted Laplacian matrix of a connected graph. Clearly $(0,1_n)$ is an ...
- 21
0
votes
0
answers
287
views
Complexity of pseudo-inverse of random matrix
Assume that $\mathbf{A}_{M\times N}$ is a sparse complex matrix. Then, what is the complexity of computation of its pseudo inverse, i.e.,
$$\mathbf{A}^{\mathrm{H}}(\mathbf{A}\mathbf{A}^{\mathrm{H}})^{-...
- 287
0
votes
0
answers
352
views
Spectral norm of difference of quadratic matrices restricted to a subspace
Say that we have two matrices $X$ and $Y$ of dimensions $(T \times N)$ with $N < T$ and $rank(X)=rank(Y)=N$. Furthermore, define a $(T \times k)$ dimensional matrix $D$ with $k<N$ and $rank(D)=k$...
- 41
0
votes
0
answers
96
views
Eigenvalues of the matrix obtained by letting some of the rows vanish, hoping for some inequality
Let $A$ be an $n \times n$ matrix. Let $A_k$ be the matrix obtained by keeping the first $k$ rows of $A$ fixed and substituting $0$ for the rows $k+1$ to $n$. To be precise, we write $A= [R_1...R_k, ...
- 1,465
0
votes
0
answers
400
views
Comparison of two similarity matrices
English is not my first language, so please excuse any mistakes.
I'm working with two similarity matrices on the same data set: Suppose I have $n$ items, and I calculated the similarity of each item ...
- 1
0
votes
0
answers
188
views
A gap problem in elementary additive combinatorics
Given $a,b\in\mathbb N$ define the set $$\chi(a,b)=\{M\in\{0,1\}^{n^a\times n^b}:\mbox{ every row of }M\mbox{ is distinct}\}.$$
Also given ${\bf{x}}=(x_1,\dots,x_{n^b})\in\mathbb Z^{n^b}$ define the ...
- 1,826
0
votes
0
answers
95
views
How to maximum L1 norm problem?
I have met a problem these days.
\begin{equation}
\underset{\omega}{\max} \quad \Vert \text{diag}(\mathbf{h}^H)\mathbf{G}^H\mathbf{\omega}\Vert_1 \\
s.t.\quad\mathbf{\omega}^H\mathbf{G}\mathbf{G}^H\...
- 171
0
votes
0
answers
208
views
Sylow subgroups of orthogonal group
According to Wikipedia (current revision) the cardinality of $O(n,q)$ depends on the properties of the field we're working over. These are the results:
We have the following formulas for the order ...
- 109
0
votes
0
answers
223
views
Solving a nonlinear matrix equation
Consider the following nonlinear matrix equation:
$B=PX^{−1}AX$
where $B$ and $P$ are a $1\times n$ row vector and $A$ is a $n\times n$ matrix which are all strictly positive, and $X=diag(x_1,...,...
- 101
0
votes
0
answers
142
views
Jordan Decomposition of Sparse matrix
Suppose we are given $n \times n$ rational matrix, $A$ with at most $k$ nonzero elements in each row and each column with $k \ll n$.
What is the best algorithm to compute its Jordan decomposition? ...
- 1,503
0
votes
0
answers
59
views
Dimension reduction
$A=({B}\otimes{I_{k}})C$ where $B$ is a $N$x$r$ matrix with rank $r$, and $C$ is a $rk$x$rk$ symmetric matrix
$M=DAE$ where $D$ is a $Nk$ x $Nk$ symmetric matrix and $E$ is a $rk$x$rk$ symmetric ...
- 31
0
votes
0
answers
107
views
Numerical error on the spectrum of a matrix
Let $Q=(q_{j,k})_{1\le j,k\le N}$ be a (Hermitian) $N\times N$ matrix with complex-valued entries. The matrix $Q$ is given numerically and the absolute error on each entry is bounded above by a (small)...
- 16.2k
0
votes
0
answers
35
views
Solutions to this equation of the form $A(t_1,t_2)x = b(t_2)$
Given two symmetric positive definite matrices $L_1, L_2\in\mathbb{R}^{n\times n}$ and a vector $w\in\mathbb{R}^n$, under what conditions does the following system of equations of the form $M_1(t_1,...
- 403
0
votes
0
answers
189
views
The algebraic connectivity of $P_n$, the path on $n$ vertices does not exceed $\frac{12}{n^2-1}$
The algebraic connectivity of $P_n$, the path on $n$ vertices does not exceed $\frac{12}{n^2-1}$.
Let algebraic connectivity of $P_n$ be denoted by $\mu$. I have proved a result that if $G$ is a ...
- 199
0
votes
0
answers
224
views
Upper bound on matrix perturbation such that all eigenvalues lie within the unit circle
Consider the matrix
$$N=\left[\matrix{\mathbb{I}_n-\epsilon L & X\\ \epsilon Y & Z}\right]$$
where $\epsilon>0$ is a small positive parameter and $Z$ is a square $m\times m$ matrix with ...
- 101
0
votes
0
answers
286
views
Gradient of the trace of the logarithm of a product
Suppose $G$ and $A$ are full rank matrices. Is there a closed-form solution for
$$\nabla_G \mbox{Tr} (A \log GG^\top)$$
when $A$ is a PSD matrix?
- 181
0
votes
0
answers
173
views
A combinatorial 0-1 matrix problem
Let $M \in \{0, 1\}^{n\times n}$.
Given a constant integer $c \ge 2$, let the number of $1$s in each row be equal to $n/c$ (assuming $c$ is a divisor of $n$).
Given a constant $\beta \in (0,1)$, we ...
- 1,677
0
votes
0
answers
89
views
Show that a certain ratio of diagonal entries dominates a certain ratio of singular values
Let $D=[d_{ij}]_{i,j=1,\ldots,4}$ be a $4 \times 4$ “density matrix”, that is, a Hermitian (possibly symmetric) positive definite matrix having trace 1—that is, the (nonnegative) diagonal entries sum ...
- 723
0
votes
0
answers
336
views
Pfaffian minors of skew symmetric matrix under perturbation
Suppose $A$ be a skew-symmetric matrix whose entries are positive numbers. A perturbation of $A$, $A'$, is obtained by adding another skew-symmetric matrix whose entries are positive integers.
My ...
- 493
0
votes
0
answers
82
views
The effect of channel error on the determinant of transmitted matrix
Assume the following matrix
$$
E:=\left(
\begin{array}{ccccc}
e_1 & e_2 & \cdots & e_{p-1} & e_{p}\\
e_{p+1} & e_{p+2} & \cdots & e_{2p-1} & e_{2p} \\
\...
- 313
0
votes
0
answers
698
views
Singular Values of Linearly Combined Matrices
I have a question related with singular values of matrix sums.
Let's assume I have matrices $A$, $B$, and $D$ (positive, semi-definite) where $D = A + B$. For singular values of $D$, I know that
$$
...
- 101
0
votes
0
answers
40
views
convex representation of a combinatorial constraint
I have an optimization problem with a weird constraint as follows. Is it possible to express it in some ways that have convex properties:
matrix $\mathbf{X}$ is either
$[1 \ 0 \ 0 \ 0 \ 0\\
\ 0 \ 0 ...
0
votes
0
answers
154
views
For which matrices deciding permutation similarity is polynomial?
Q1 For which matrices deciding permutation similarity is polynomial?
It is not easier than graph isomorphism (and very likely is equivalent to it).
If necessary, assume the entries are nonnegative ...
- 25.4k
0
votes
0
answers
114
views
A linear combination problem
Given $0/1$ $n\times n$ matrix $M$.
Suppose we have $2$ vectors $\lambda,\mu\in\Bbb R^{1\times n}$ such that both
$$\lambda M\in\{0,1\}^{1\times n}$$
$$M\mu'\in\{0,1\}^{n\times 1}$$
holds with $'$ ...
user76479
0
votes
0
answers
160
views
$l_{\infty}$ norms of matrix perturbations
Say $B$ is a real symmetric matrix of dimension $n$ and $A$ is another real symmetric matrix of the same dimension.
What needs to be the bounds on (which?) norm of $B$ to ensure that $\lambda_{max}(...
- 1,893
0
votes
0
answers
206
views
Finding a "special" non singular submatrix
Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ (...
- 59
0
votes
0
answers
90
views
Derivative of a conjugation of matrices
Let $\mathcal{M}_n$ be the space of complex $n\times n$ matrices. Let $\Phi\colon \mathbb{D}\to \mathcal{M}_n$ and $\psi \colon \mathbb{D}\to \mathcal{M}_n$ be holomorphic functions. Consider the ...
- 758
0
votes
0
answers
201
views
Range of a trace preserving completely positive projection
I'm working in $M_n(\mathbb{C})$, the algebra of complex $n\times n$ matrices. I managed to build a completely positive, trace preserving, star preserving, projection $P$. That is
$$\text{Tr}(P(A)) = ...
- 515
0
votes
0
answers
123
views
A quantity associated with an algebraic variete
Let $P:\mathbb{C}^{n}\to \mathbb{C}$ be an irreducible homogenous polynomial.
Is there a geometric or algebra geometric interpretation for the following quantity:
The maximum number $k$ such that ...
- 356
0
votes
0
answers
83
views
Bits of precision matrix reconstruction
We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$.
Suppose we have diagonalized using $LMR=D$.
I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of $\widetilde{...
- 13.9k
0
votes
0
answers
161
views
Way to parameterise sparse multi diagonal matrix
I have an NxN matrix S that looks like this: $$ S^{-1} = K^{-1} + \Lambda $$
where N is a multiple of 3, both K and S are positive definite matrices, and Lambda is
$$
\Lambda = \begin{bmatrix}
x &...
- 1
0
votes
0
answers
259
views
Zariski dense subgroups and conjugates
Let $H \leq \mathrm{SL}_3(\mathbb{Z})$ be a finitely generated subgroup which is not Zariski dense, and let $g \in \mathrm{SL}_3(\mathbb{Z})$. Must there be some $a \in \mathrm{SL}_3(\mathbb{Z})$ such ...
- 11.3k
0
votes
0
answers
227
views
Canonical forms of symmetric/skewsymmetric quaternionic matrix
$A$ belongs to $n$-dimensional quaternion symmetric matrix, in the sense that $A=A^T$, where $T$ means transpose. Under transformation $U$, $A\rightarrow U\cdot A\cdot U^T$, where $U$ is $n$-dim ...
- 293
0
votes
0
answers
61
views
Solution of a nonlinear system of two equations
Given the matrix $A_{M,N}$ with $N\gt M$, the vector $y$, I have to find the vectors $x$ and $u$, satisfying the following equations:
$$D(x)x=A^Tu$$
$$y=Ax$$
where: $$D(x) = \left| \begin{array}{ccc}
\...
- 399
0
votes
0
answers
244
views
Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$
Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix $...
- 25.4k
0
votes
0
answers
141
views
Property of quasipositive matrices
I saw this theorem stated in a paper without proof and I have difficulty proving it.
If $A$ is an $n\times n$ matrix with non-negative off-diagonal entries, let $s(A)$ be the real eigenvalue such ...
- 143
0
votes
0
answers
704
views
expected matrix inverse of circulant plus diagonal matrix with chi-square variables
Let $R$ be a semi-definite $N\times N$ circulant Toeplitz matrix and let $N\to \infty$.
Let $D$ be an $N\times N$ diagonal matrix where the elements on the main diagonal are independent chi-square ...
- 96
0
votes
0
answers
115
views
a very elementary question on the conjugated matrices
Let $A$ and $B$ two matrices in $GL_{n}(K[[\pi]])$, regular semisimple on $GL_{n}(K((\pi)))$, with $K$ an algebraically closed field of characteristic zero .
We suppose that they have the same ...
- 3,472