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.

Filter by
Sorted by
Tagged with
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) &...

1
3 4
5
6 7
63