Questions tagged [matrices]
Questions where the notion matrix has an important or crucial role (for the latter, note the tag matrix-theory for potential use). Matrices appear in various parts of mathematics, and this tag is typically combined with other tags to make the general subject clear, such as an appropriate top-level tag ra.rings-and-algebras, co.combinatorics, etc. and other tags that might be applicable. There are also several more specialized tags concerning matrices.
3,106
questions
2
votes
4
answers
283
views
Find a square, stochastic matrix of odd size, not a permutation matrix, with an eigenvalue other than 1 on the unit circle
...or prove that none exists.
Note that such a matrix $M$ couldn't be primitive, so there would be at least one entry equal to zero in every power $M^k$ (Perron-Frobenius theory).
Preferably the ...
2
votes
0
answers
171
views
Is every nearly rank-1 doubly stochastic matrix a product of pairwise averaging matrices?
A doubly stochastic matrix is a square matrix with non-negative real entries where the sum of each row is $1$ and the sum of each column is $1$. A pairwise averaging matrix is a matrix of the form $tA+...
-1
votes
1
answer
420
views
What is wrong with the argument that zero permanent is polynomial?
This Lecture summarizes some well known facts about $\#P$ completeness of permanent.
Given a CNF formula $\phi$ on $n$ variables, they construct
matrix $A$ such that:
$$perm(A)=4^{3m} \#SAT(\phi)$$
...
34
votes
3
answers
3k
views
Quickly determining if a matrix has any PSD completion
Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?
Slightly more precisely: for simplicity let's assume ...
0
votes
0
answers
50
views
Rank of Coxeter matrix
Let $Q$ be a quiver and $\Phi_Q$ be the Coxeter matrix of $Q$.
Then $\Phi_Q\pm I$ are full-rank?
20
votes
2
answers
17k
views
Complexity of linear solvers vs matrix inversion
Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...
1
vote
1
answer
164
views
Diagonally dominant matrix via rows permutation
Diagonally dominant matrices are required in many linear algebra algorithms such as the Gauss-Seidel algorithm.
Some matrices can be made diagonally dominant by permuting its rows and others cannot.
...
6
votes
1
answer
3k
views
Minimum and maximum eigenvalue
I don't know if this is the right place to post this question, but I find it interesting and have not gotten an answer elsewhere. If it violates any rules, I will gladly delete it.
Let $\Lambda$ be ...
1
vote
0
answers
147
views
Fastest algorithm for finding the closest semi-definite matrix?
Given a real-valued, symmetric matrix $A \in \mathbb{R}^{n \times n}$, I'm interested in finding the closest positive semi-definite matrix $X^*\in \mathbb{R}^{n \times n}$:
$$
X^* = \mathop{\text{...
3
votes
1
answer
681
views
Computational complexity of low rank SDP
Suppose we are given a general semidefinite program (SDP) of the form with an additinal rank requirement
\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{...
4
votes
2
answers
428
views
Completing partial matrix to a positive definite matrix
Is the following problem known? Suppose one is given some of the entries of an $n \times n$ matrix $A$ over $\mathbb{R}$, so that the given entries are symmetric. Can one assign values to the ...
6
votes
1
answer
2k
views
SDP formulation of noisy low-rank matrix completion
Exact low rank matrix completion using nuclear norm minimization can be formulated as a semidefinite program (SDP). Following the notation in the paper, a convex problem for noisy matrix completion ...
1
vote
0
answers
85
views
Keshavan-Montanari-Oh matrix completion — clearing step
I am trying to implement the algorithm for matrix completion proposed by Keshavan, Montanari and Oh (2009). It consists of three steps:
Trimming which nulls some rows and columns to make the high ...
1
vote
0
answers
220
views
Nonunique low-rank matrix completion from a few entries
Suppose we want to have a good approximation for the following NP-hard problem
$$\min_{\bf X} \operatorname{rank}({\bf X}) \text{ s.t. } \mathcal{A}({\bf X}) = {\bf b}, {\bf X} \succeq 0$$
where ${\bf ...
2
votes
1
answer
275
views
Possible pathological properties of positive definite matrix
Suppose $A$ is a positive definite matrix such that$$ I \preceq A \preceq 1.01I.$$ Is it possible that $\sum\limits_{i=1}^n A_{1i}$ can be arbitrarily large?
17
votes
1
answer
713
views
A matrix completion problem
In their paper, Corners of normal matrices, Rajendra Bhatia and Man-Duen Choi asked the following question:
Given a matrix pair $(B,C)$ where $B,C∈M_n$, does there exist matrices $A,D ∈ M_n$ such ...
11
votes
3
answers
8k
views
Eigenvectors of a symmetric positive definite Toeplitz matrix
I wish to efficiently compute the eigenvectors of an n x n symmetric positive definite Toeplitz matrix K. A full eigendecomposition would be even better.
Although I assumed this would be a well ...
5
votes
2
answers
696
views
Matrices with same eigenvalues
This question is a more precise version of this question.
Let's assume we have the matrix
$$\left(
\begin{array}{ccccc}
0 & a & 0 & 0 & 0 \\
f & 0 & b & 0 & 0 \\
0 &...
3
votes
1
answer
252
views
Eigenvalues two-fold degenerate
Consider the matrix $$A:=\left(
\begin{array}{cccc}
0 & a & 0 & 0 \\
f & 0 & b & 0 \\
0 & e & 0 & c \\
0 & 0 & d & 0 \\
\end{array}
\right)$$
I ...
19
votes
1
answer
2k
views
Smallest eigenvalue of a tricky random matrix
While experimenting with positive-definite functions, I was led to the following:
Let $n$ be a positive integer, and let $x_1,\ldots,x_n$ be sampled from a zero-mean, unit variance gaussian. Consider ...
0
votes
1
answer
269
views
Positive definite Hermitian matrices of countable rank
Say that a $\omega\times \omega$ Hermitian matrix $A$ is positive semidefinite of rank $n$ if there exists a $\omega\times n$ complex matrix $B$ such that $A=B B^\dagger$ where $^\dagger$ denotes the ...
4
votes
0
answers
95
views
A question on products of linear combinations of complex matrices
Suppose that $A_1, \dots , A_n, B_1, \dots , B_n \in \Bbb C^{d \times d}$ and that, for every $x \in \mathbb{C}^n$, the following holds
$$\left( \sum_i x_i A_i \right) \left( \sum_i x_i A_i \right)^{...
17
votes
2
answers
5k
views
Nonvanishing of Jacobians implies global injectivity?
I am interested in obtaining injectivity of a $C^1$ map from the nonvanishing minors of its Jacobian matrix. Here is a brief history of the topic.
In 1953, Samuelson asked the following:
If the ...
1
vote
2
answers
195
views
On a matrix trace inequality
Let $\mathcal H(n)$ be the set of $n\times n$ Hermitian matrices, and $\mathcal S(n) \subset \mathcal H(n)$ be the subset of density matrices, i.e., $A \in \mathcal S(n)$ iff $A$ is Hermitian, ...
1
vote
0
answers
124
views
QR algorithm for eigenvalues and eigenvectors of large symmetric matrices
I am trying to write a QR algorithm in Python for eigenvectors and eigenvalues finding for large symmetric matrices,
My initial thought was to use Householder transformation with a Wilkinson shift ...
2
votes
0
answers
87
views
decidability special case of column generation problem
I have the following problem:
Input: sub-spaces $V_1, \dots, V_d$ of $\mathbb{Z}^{d}$
Question: are there $v_i \in V_i$ such that the matrix $(v_1, \dots, v_d)$ has determinant $\pm 1$ (equivalently, ...
5
votes
1
answer
211
views
Commuting matrices and cyclic modules
Let $A, B\in M_n(\mathbb{C})$ be matrices that commute. We suppose that there exists a vector $v\in\mathbb{C}^{n}$ such that $(\mathbb{C}[A,B]).v$ generates $\mathbb{C}^{n}$. We call such a pair a ...
0
votes
0
answers
116
views
Diagonalizing a specific case of symmetric block matrix
Let's consider the following block matrix
$$ M = \begin{pmatrix}D&A^T\\A&-D\end{pmatrix},$$
where $A$ and $D$ are $n \times n$ matrices. The diagonal matrix $D$ is defined by $D_{kk} = k \...
2
votes
0
answers
70
views
The probability that the dominant eigenvalue of a random real matrix is real
Let $X_n$ be an $n\times n$ real matrix where the entries in $X_n$ are independent, normally distributed, have mean $0$, and variance $1$. Suppose that $\lambda_1,\dots,\lambda_n$ are the eigenvalues ...
3
votes
1
answer
179
views
Results on Boolean matrices
Matrices with entries in the finite field of two elements $\mathbb{F}_2$, and with the usual operations of matrix addition and multiplication, have been intensively studied, especially due to their ...
3
votes
2
answers
3k
views
Inverse of particular lower triangular matrix
I have an $n \times n$ lower triangular matrix $A$ where
$$A_{i,j} = {\bf x}_i{\bf x}_j^H,\quad i>j$$
$$A_{ii}=1, \quad 1 \leq i \leq n,$$
and ${\bf x}_i$ is a $1 \times k$ (row) vector, where $...
1
vote
1
answer
125
views
Matrix transformation that always works?
Consider the matrix
$$A_2:= \begin{pmatrix} a & b_1 \\ b_2 & a\end{pmatrix}.$$
Let $\sigma_2 = \begin{pmatrix} 0 & i \\ -i & 0 \end{pmatrix}$, then
$$\sigma_2 A_2 \sigma_2 = \begin{...
0
votes
0
answers
107
views
What are the properties of square-matrix algebra with this equivalence class?
Consider the set of all square matrices with the following equivalence class:
$\mathbf{A}\sim\mathbf{A}\otimes\mathbf{I}_n$ (or, alternatively, as user @M.G. proposed, $\mathbf{A}\sim\mathbf{I}_n\...
2
votes
1
answer
1k
views
Eigenvalues of a rank-one update of a symmetric matrix
I have a matrix $A$ $(n\times n)$ with eigenvalues $\lambda_i$, then I add another matrix to it as: $A+xx^\top$ where $x$ $(n\times 1)$ is a column vector.
and also $A=yy^\top$ with $y$ a $(n-1)$ rank ...
1
vote
0
answers
153
views
Eigenvalue decomposition of normalized adjacency matrix
Let $A$ be an adjacency matrix of undirected graph $G$, where $G$ is a connected graph. The normalized adjacency matrix is defined as $\hat{A}=D^{-1/2}AD^{-1/2}$, where $D$ is degree matrix of graph $...
1
vote
1
answer
193
views
Symmetric Integral Matrices
Let $SM_n(R)$ be the set of $n\times n$ symmetric matrices with entries in a ring $R$ and let $A\sim B$ for such matrices if $A=C^T\cdot B\cdot C$ for some $C\in SL(n,R).$ It is an equivalence ...
1
vote
0
answers
23
views
Linear independent matrix space $M_i^{+}M_j$
Under what condition of $k,m,n$, we can have $k$ matrices $M_1,\cdots,M_k\in \mathbb{C}^{m\times n}$ such that the $k^2$ matrices $M_i^{+}M_j$ are linear independent? Here, $M^+$ denotes the hermitian ...
8
votes
1
answer
399
views
Big triples in a matrix
Consider an $n\times n$ real matrix $A=(a_{ij})$ with non negative entries. Assume that
- the sum of the three largest entries in each row is a constant $R$ (the same for all rows),
- the sum of the ...
0
votes
0
answers
30
views
Normalization of eigenvectors after multiplying with phases
This question is in essence a follow up to the question.) :
Suppose we normalize the three columns of the unitary matrix before multiplying with the
phase matrix. Then after multiplying with the phase ...
18
votes
2
answers
483
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\...
3
votes
1
answer
158
views
Approximations of the spectral radii of completely positive superoperators
Let $V$ be a finite dimensional complex Hilbert space. Let $L(V)$ denote the collection of all linear operators from $V$ to $V$. An operator $\mathcal{E}:L(V)\rightarrow L(V)$ is said to be positive ...
3
votes
0
answers
82
views
Exterior powers of the Cartan matrix and Dyck paths
(This question can be formulated purely combinatorially in terms of Dyck paths, which is done in the second part of the question. But I am more interested whether this can be explained by some sort of ...
2
votes
1
answer
201
views
A subgroup of $\mathrm{SL}_n(\mathbb{Z}/p\mathbb{Z})$
Let $p$ be an odd prime, and consider the group
$$\{U\in \operatorname{SL}_n(\mathbb{Z}/p\mathbb{Z}) : U^{t}U=I \bmod p \}\subseteq \operatorname{SL}_n(\mathbb{Z}/p\mathbb{Z}).$$
I wonder what is the ...
2
votes
2
answers
151
views
expectation and variance of the norm of a random matrix
Suppose $X \in \mathbb{R}^{n \times d}$ is a random matrix where $n > d$. Given a matrix $A \in \mathbb{R}^{n \times n}$ such that $AX$ is a zero matrix in expectation, i.e., $\mathbb{E}_{X}[AX] = ...
1
vote
0
answers
69
views
If $\hat{D}$ minimizes trace over all $D+ B \succeq 0$, then is $\hat{D}_{ii} \leq \sum_{j} |B_{ij}|$ for each $i$?
Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
Let $\hat{D}$ be a solution to the SDP that minimizes $tr(...
8
votes
2
answers
1k
views
Geometric interpretation of the Desnanot–Jacobi Identity
Given a square $n\times n$ matrix $M$, let $M_i^j$ denote the $(n-1)\times(n-1)$ matrix obtained from M by omitting the $i$-th row and $j$-th column of $M$.
The Desnanot–Jacobi Identity states
$$\det(...
2
votes
1
answer
317
views
On a theorem of Carlson on the necessary and sufficient condition for a matrix to have $m$ real eigenvalues
Background: In the physics of open quantum systems the Lindbladian $\mathcal{L}$ governs the evolution of quantum states through the Lindblad master equation.
The Lindblad operator usually has ...
0
votes
1
answer
184
views
Faulty algorithm for simultaneous diagonalization?
I found a simple algorithm for simultaneous diagonalization of two commuting matrices (Nordgren - Simultaneous Diagonalization and SVD of Commuting Matrices), which seemed to be well-founded. For ...
1
vote
0
answers
88
views
Higher dimensional Cauchy interlacing theorem
If $A$ is a Hermitian matrix and $A_j$ the principal minor with the $j$ row and column deleted and $\phi_A(x)$ the characteristic polynomial. The Cauchy interlacing iheorem states that the roots of $\...
2
votes
1
answer
93
views
Summation of rows of a matrix P^k is decreasing with the power k
I have the following $(n+1)\times (n+1)$ matrix
$$P = \begin{bmatrix}
f(0) & g(0) & 0 & 0 & 0 & \dots & 0\\
f(1) & 0 & g(1) & 0 & 0 & \dots & 0\\
f(2) &...