All Questions
Tagged with linear-algebra inequalities
176 questions
8
votes
1
answer
290
views
Distance from nonnegativity of some orthonormal vectors
Suppose that $1 < k < n$. Does there exist a constant $\beta > 0$, such that for every $k$ orthonormal vectors $f_1,\ldots,f_k \in \mathbb R^n$,
there exist $k$ orthonormal vectors with ...
- 128k
8
votes
0
answers
577
views
A rank inequality
Suppose
$$M := \begin{bmatrix}
M_{11} & \cdots &M_{1d} \\
\vdots & \ddots & \vdots \\
M_{d1} & \cdots & M_{dd}
\end{bmatrix}$$
is a $d \times d$ block matrix such that
$$M_{...
8
votes
0
answers
492
views
Strange determinant inequality $\det(C+ xA) \det(C-xA) \le (\det C)^2$
Let $A$ be an all-one $3$-by-$3$ matrix, let $C$ be a $3$-by-$3$ matrix, and let $x$ be a real number. How might one prove the following inequality?
$$\det(C+ xA) \det(C-xA) \le (\det C)^2$$
5
votes
0
answers
586
views
A minimal eigenvalue inequality
Suppose $A$ is an $n\times n$ real symmetric positive definite matrix. Let $A^{(-1)}_{i,j}$ be the $n\times n$ matrix the entries $(i,i),\,(i,j),\,(j,i),\,(j,j)$ of which equal to the corresponding ...
- 2,239
1
vote
1
answer
1k
views
Inequality between the singular values for a sum of two matrices
For two complex matrices $A,B \in \mathbb{C}^{n\times m}$ how to prove that:
\begin{equation}
\overline{\sigma}(B-A) \ge \underline{\sigma}(B) - \underline{\sigma}(A)
\end{equation}
where $\underline{...
- 109k
4
votes
1
answer
256
views
An elementary inequality for graph Laplacians
Let $G$ be an arbitrary graph on $n$ vertices and $\mathcal L$ be its Laplacian.
I need to show that
\begin{equation}\tag{$*$}
\langle \mathcal Lx,\mathcal L(|x|^{p-2}x)\rangle_{\mathbb R^n}\ge 0\...
- 3,388
9
votes
1
answer
804
views
A singular value-eigenvalue inequality
Singular value or eigenvalue problems lie at the center of matrix analysis. One classical result is
$$\lambda_{j}(X^{*}X+Y^{*}Y)\geq 2\sigma_j(XY^*)$$
for $j \in \{1, \ldots, n\}$, where $\lambda_j(\...
- 2,753
0
votes
1
answer
75
views
Equivalent linear inequalities system - Coefficients bound?
Just having some difficulties with this system of inequalities...
We know E is a system of m linear inequalities of the form:
a1,1x1+ ··· +a1,nxn ≤ b1
...
am,1x1+ ··· +am,nxn ≤ bm
And E' an ...
- 54.2k
3
votes
0
answers
77
views
A concentration problem of product of matrices
Let $A$ be an $n \times m$ matrix with non-negative entries and $B \in \mathbb{R^{n\times n}_{\geq 0}}, C \in \mathbb{R^{m\times m}_{\geq 0}}$ be random matrices where B and C are both symmetric and ...
- 195
1
vote
0
answers
110
views
Tail bound without independence
Suppose $X_i , X_j\in \mathbb{R}^d$ are gaussian vectors and $A$ is an $n\times n$ symmetric PSD matrix where $A_{ij} = f(\|X_i-X_j\|_2), \quad i,j\in 1,\ldots,n\;$ for some non-negative Lipschitz ...
- 195
8
votes
1
answer
726
views
A direct proof of a property of symmetric 2x2-determinants
Let $f(a,b,c)=\det\begin{pmatrix}a &b\\ b& c\end{pmatrix}\in\mathbb{R}[a,b,c]$ be the determinant of a $2 \times 2$ real symmetric matrix.
Let $f(x_i,y_i,z_i)\geq 0$, $x_i\geq 0$, $z_i\geq 0$ ...
- 14k
14
votes
2
answers
574
views
A simple but curious determinantal inequality
Let $A$ and $B$ be $n\times n$ Hermitian positive definite matrices and $k>0$ real. Then $A^k$ is well-defined and experimentally, we have $$\det(A^k+BABA^{-1})\geqslant \det(A^k+BA^{-1}BA),$$or ...
- 28.6k
0
votes
2
answers
160
views
A matrix between vectors, and inequality!
I have an inequality as follows
$$s^T\phi\leq -|s|^TA$$
where $s$, $\phi$ and $A$ are vectors with appropriate dimensions. I want to prove that this inequality holds for the following too
$$s^TM\...
- 73
1
vote
0
answers
282
views
Strict monotonicity of conditional variances
Let $K \geq 2$ be a positive integer and $C$ be any $K \times K$ non-singular matrix (if necessary, can assume that all $K$ rows of $C$ are needed to span the coordinate row vector $e_1'$). For ...
- 3,958
1
vote
1
answer
95
views
Is it true that $B \leq I \rightarrow B^2 \leq I$ (or higher powers) for positive semidefinite $B$, mimicking positive scalars? [closed]
If we know that $B \geq 0 $ (positive semidefinite) and that $I-B \geq 0$, is it necessarily true that $I-B^2 \geq 0$?
- 1
6
votes
0
answers
587
views
Lower bound on the sum of singular values for a sum of Hermitian matrices
Denote the eigenvalues of an $n\times n$ matrix $\mathbf{X}$ by $\lambda_i(\mathbf{X})$ and its singular values by $\sigma_i(\mathbf{X})$, $i=1,\ldots,n$. When $\mathbf{X}$ is Hermitian, we know that $...
- 159
12
votes
2
answers
4k
views
Prove that matrix is positive definite
I faced a hard question in kernel methods theory, which I can't answer for about one week. Initially it was formulated in terms of positive valued functions, but it could be reformulated easier:
Let $...
- 3,946
6
votes
2
answers
476
views
Is there a trace inequality for the product of a sequence of hermitian postive definite matrices?
Let $A$ and $B$ be two Hermitian matrices with positive eigenvalues.
Let $k>0$ be a integer.
Let $P=(P_1,P_2,\dots,P_{2k})$ be a sequence of $k$ $A$s and $k$ $B$s in any given order.
Do we have
${...
- 28.6k
16
votes
2
answers
2k
views
Bounding the matrix norm of a commutator $[A,B]$ in terms of the norms of $A$ and $B$
The setup is as in this question:
Given a norm $N$ over ${\bf M}_n(\mathbb C)$, it is a natural question to find the best constant $C_N$ such that
$$N([A,B])\le C_N N(A)N(B),\qquad\forall A,B\in{\bf M}...
CommunityBot
- 1
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
35
votes
3
answers
4k
views
A curious determinantal inequality
In my study, I come across the following curious inequality, which I do not know a proof yet (so I am asking it here).
Let $A, B$ be $n\times n$ (Hermitian) positive definite matrices. It is very ...
- 1,748
3
votes
1
answer
248
views
Log-convexity of conditional variances
Let $K$ be a positive integer and $C$ be any $K \times K$ non-singular matrix. For positive real numbers $q_1, \dots, q_K$, define
$$\Sigma(q_1, \dots, q_K) = CC' + diag(\frac{1}{q_1}, \dots, \frac{1}...
- 28.6k
1
vote
1
answer
121
views
Probability for high mutual coherence on all subsets of a Gaussian vector set
We examine as set of independent normal vectors:
$$ \forall i \in [N]\triangleq \{1,\dots,N\}:\,\mathbf{x}_{i}\sim\mathcal{N}\left(0,\mathbf{I}_{d}\right)$$
For any $\epsilon>0$ and $K\leq N$, we ...
- 968
2
votes
0
answers
147
views
Is the following inequality true for the norm of Moore-Penrose pseudoinverses?
Let $L$ be a real, positive semi-definite, symmetric, square matrix, with pseudoinverse $L^{+}$. It can be shown for the operator norms $||.||_{op}$ that: if $L$ is invertible and $||I - L||_{op} < ...
- 1,467
10
votes
1
answer
3k
views
Reverse Minkowski (and related) Determinant Inequalities
For positive semidefinite matrices $A,B,C \in \mathbb{R}^{n\times n}$, the following inequalities are well known:
$$(\det(A+B))^{1/n} \geq (\det A)^{1/n} + (\det B)^{1/n} $$
and
$$\det(A+B+C) + \...
CommunityBot
- 1
1
vote
1
answer
161
views
An inequality regarding a recursive relation
I have the following problem. I will be thankful for receiving any hint or any comments.
Suppose $p\in(0,1)$ and $q=1-p$. Given the recursive relation: for $n>k$,
$$h(n)=q h(n-1)+p q^{k-1} h(n-k)$...
- 2,251
5
votes
1
answer
2k
views
Upper bound of the largest eigenvalue of a PSD block matrix in terms of blocks
Let $\mathbf A=\left[\begin{matrix}\mathbf A_{11}&\mathbf A_{12}\\ \mathbf A_{21}&\mathbf A_{22}\end{matrix}\right]$ be a positive semi-definite matrix, $\mathbf A_{ij}\in\mathbb C^{n\times n}...
- 61.9k
1
vote
0
answers
55
views
On the Lowener-Heinz inequality
I know that for two symmetric positive semi-definite (non-diagonal) matrices $A,B$, the inequality asserts that the following does not hold for all $p > 1$
$$A \succeq B \succeq 0 \Rightarrow A^p \...
- 11
6
votes
1
answer
238
views
Positive semidefinite ordering for covariance matrices
Suppose that X and Z are matrices with the same number of rows. Let
$$ D = \left[\begin{array}{cc} X' X & X'Z \\ Z'X & Z'Z \end{array} \right]^{-1} - \left[\begin{array}{cc} (X' X)^{-1} & ...
- 128k
18
votes
1
answer
1k
views
A curious eigenvalue inequality
Suppose $A, B$ are positive definite Hermitian matrices, $U$ is a unitary matrix such that $AUB$ is Hermitian. The spectral radius of a square matrix $X$ is denoted by $\rho(X)$. In my study, I ...
- 98
2
votes
1
answer
380
views
Bounding entries of the inverse of certain zero-one matrices
It is known that the entries of the inverse of an (invertible) $n \times n$ zero-one matrix $A$ can grow exponentially in $n$. See this MO question:
Bounding the absolute sum of entries of the ...
CommunityBot
- 1
13
votes
2
answers
1k
views
A matrix norm inequality
Suppose that $A, B$ are Hermitian positive definite matrices of the same order and $0\le p\le 1$. Using a standard approach in matrix analysis, one can show that
$\|A^{1-p}B^p\|\ge \|A\sharp_p B\|$, ...
- 1,748
3
votes
1
answer
428
views
Inverse Hadamard determinant inequality
As far as I remembered there is an inverse Hadamard inequality for the determinant of the form
$$
|D|>\prod_j \sqrt{(a_{jj}^2-\sum_{i\neq j}a_{ij}^2)}
$$
providing all values in $(\cdot)>0$.
...
- 2,286
2
votes
2
answers
297
views
Looking for (information about) long diamonds
I was given an open problem as a birthday present recently. While I can probably handle spoilers at this point, what I really want are literature and other references. Also acceptable would be ...
- 3,946
4
votes
0
answers
676
views
Weyl-type inequality for non-Hermitian matrices?
What is the weakest known condition under which a Weyl-type eigenvalue perturbation inequality holds? Does some analogue hold for normal matrices, for example?
- 1,590
13
votes
1
answer
1k
views
An inequality for the spectral radius of matrices used by J. Bochi
I am interested in the history of an inequality for the spectral radius of a $d\times d$ real or complex matrix, which occurs in Jairo Bochi's 2002 article Inequalities for numerical invariants of ...
- 6,206
12
votes
0
answers
218
views
Which ordering of factors is needed to obtain this kind of determinantal inequalities?
Let $A$ and $B$ be $n\times n$ Hermitian positive definite matrices. The curious determinantal inequality given here, which can be stated as $$\det (A^{4}+ ABBA+BAAB+B^{4})\ge\det(A^{4}+ AABB+BBAA+B^{...
CommunityBot
- 1
17
votes
1
answer
2k
views
Hlawka inequality for determinants of positive definite matrices
It is mentioned here that if $A, B, C\in M_{n}(\mathbb C)$ are positive semidefinite, then $$\det (A+B+C)+\det C\ge \det (A+C)+\det (B+C)$$ (quoted from this article) and the special case ($C=\bf 0$) $...
CommunityBot
- 1
0
votes
1
answer
246
views
Matrix equation
Let $A$ be $k\times n$ matrix i.e., $A=(a_{1},\ldots, a_{n})$ where $a_{j} \in \mathbb{R}^{k}$, $rank(A)=k$ and $1\leq k \leq n$. Let $q=(q_{1},\ldots, q_{n})\in\mathbb{R}^{n}$ be such that $0<q_{j}...
- 3,741
2
votes
0
answers
133
views
Vector inequation problem [closed]
$${A_i} = \left( {\begin{array}{*{20}{c}}{{A_{i1}}}\\{{A_{i2}}}\\ \vdots \\{{A_{in}}}\end{array}} \right),{B_i} = \left( {\begin{array}{*{20}{c}}{{B_{i1}}}\\{{B_{i2}}}\\ \vdots \\{{B_{in}}}\end{array}}...
- 31
0
votes
1
answer
355
views
Lower bound on Spectral Gap of Rank one + Diagonal
For some $x\in\mathbb{R}^n, \|x\|_2^2=1$ and $\alpha\geq 0$, consider the positive semi-definite matrix
$$
X_\alpha := xx^T + \alpha\sum_{k=1}^nx_k^2e_ke_k^T.
$$
Suppose for simplicity that the ...
CommunityBot
- 1
1
vote
0
answers
85
views
What are good bounds on ratios of subdeterminants?
Let $A$ be a symmetric matrix and $A_i$ be the matrix obtained from $A$ by dropping the $i^{th}$ row and column. Then what are some good bounds on the value of $\frac{det(A_i)}{det(A)}$ ?
Using the ...
- 1,893
2
votes
1
answer
843
views
Bounds on Hilbert-Schmidt norm of difference of products of matrices
I suspect the following is well-known, but don't know of a reference (and it is not close to the area I normally work in).
I have two sequences of matrices $Q_{1},\ldots,Q_{k}$ and $R_{1},\ldots,R_{k}...
- 20.2k
1
vote
0
answers
396
views
Bound of spectral radius of polynomial of a complex matrix
I am trying to prove or disprove the following inequality.
$$ ||P(A)||_2\leq 2 \max_{\alpha\in W(A)}| P(\alpha)|,$$
where $P(\cdot)$ is a complex polynomial, $A\in \mathbb{C}^{n\times n}$ and $W(A)...
- 163
0
votes
1
answer
72
views
Characterisation of a matrix ordering property
Let $n$ be a positive integer; we consider all matrices mentioned henceforth to be $n$-by-$n$ matrices. Let $A$ and $B$ be matrices wherein all entries are nonnegative (such matrices will be called ...
- 54.2k
1
vote
1
answer
358
views
Matrix Submodular Inequality
Given $a,b,x > 0$ I know following the submodularity property holds:
\begin{align}
\frac{1}{a} - \frac{1}{a+x} \geq \frac{1}{a+b} - \frac{1}{a+b+x}
\end{align}
My question is, does this property ...
- 54.2k
1
vote
0
answers
112
views
Tools to bound the singular values of a finite sum of random matrices from below?
Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...
- 111
0
votes
0
answers
68
views
Estimate bounds on Minkowski distance from point to a segment in Lp space
Assumptions
Let
$L_p(x,y)=(\sum_i|x_i - y_i|^p)^{1/p}$ (Minkowski metric),
$a,b$ be arbitrary $n$-dimensional points,
$c$ be a point that satisfies $L_p(a,b) = L_p(a,c) + L_p(c,b)$, i.e., a point ...
CommunityBot
- 1
3
votes
0
answers
158
views
Worst-Case Solution to (Stochastic) Matrix Inequality
EDIT: Some specific conjectures added.
This problem comes with an associated stochastic process, but I phrase everything as linear algebra in case somebody from a non-probability community has seen ...
- 31
1
vote
0
answers
225
views
Is there an improvement for the Schur-Horn inequalities for positive semi-definite matrices?
By the Schur-Horn inequality I am thinking of the statement that for any Hermitian matrix $H$ its diagonal n-tuple $(H_{11},H_{22},..,H_{nn})$ for any choice of basis lies in the convex hull of the $n!...
- 1,893