All Questions
Tagged with linear-algebra inequalities
176 questions
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
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 ...
- 13.4k
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
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\...
- 29
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 ...
- 765
13
votes
2
answers
794
views
Distance of vectors versus distance of their difference vectors
For any given $x \in \mathbb{R}^n$, let $\nabla{x} \in \mathbb{R}^{n \choose 2}$ be the vector whose $\{i,j\}$-th entry is $|x_i-x_j|$. I think the following claim is true.
Claim. If $f, g \in \...
- 519
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$?
- 11
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 $...
user99354
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
${...
- 397
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
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}...
- 765
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}...
- 13.4k
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) + \...
- 716
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)$...
- 11
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}...
- 103
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} & ...
- 1,068
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 ...
- 1,081
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 ...
- 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$.
...
- 1,550
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
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 $...
- 907
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?
- 6,541
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
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 ...
- 13k
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^{...
- 13.4k
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
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
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 ...
- 205
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}...
- 98
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 ...
- 345
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 ...
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
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 ...
- 101
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
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,946
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$) $...
- 13.4k
16
votes
0
answers
809
views
Determinant inequality involving Hermitian, positive definite matrices
Let $A,B,C\in M_{n}(\mathbb C)$ be Hermitian and positive-definite matrices such that $A+B+C=I_{n}$.
Show that
$$\det\left(6(A^3+B^3+C^3)+I_{n}\right)\ge 5^n\det(A^2+B^2+C^2)$$
This question has been ...
- 269
2
votes
1
answer
1k
views
An inequality involving traces and matrix inversions
The following question kept me wondering for some time:
Given the symmetric matrices $A,B,C\in\mathbb{R}^{n×n}$ where $A$ and $C$ are positive definite (hence invertible), and $B$ is positive ...
- 53
19
votes
1
answer
856
views
A possible extension of a determinant inequality
It is well known that if $A, B$ are positive semidefinite matrices, then $$\det (A+B)\ge \det A+\det B.$$
I am considering a possible extension of this result. Let $\mathbb{M}_m(\mathbb{M}_n)$ ...
- 1,748
5
votes
0
answers
2k
views
A stronger Cauchy-Schwarz inequality for traces of compression matrices
Assume that $A$ and $B$ are contractions, so
$I-AA^T$ and $I-BB^T$ are positive-definite matrices. Let
$C=(I-AB^T)^{-1}(I-AA^{T})(I-BA^{T})^{-1}$, and show that:
$$Tr\left(\frac{1}{1-AA^T}\right)...
- 4,280
3
votes
1
answer
735
views
A similar Cauchy-Schwarz inequality with linear-algebra
Let $A$ be matrix in $M_{n}$ (i.e., $n\times n$ complex matrices), and $\|A\|\le 1$, we call it a contraction.
Assume that $A$ and $B$ are contractions such that
$I-AA^*$ and $I-BB^*$ are positive-...
- 4,280
26
votes
3
answers
17k
views
Hölder's inequality for matrices
I was wondering if the Hölder's inequality was true for matrix induced norms, i.e. if
$$\|AB\|_1 \leq \|A\|_p\|B\|_q, \quad\forall p,q \in [1,\infty] \text{ s.t. } \tfrac{1}{p}+\tfrac{1}{q} = 1.$$
But ...
- 837
9
votes
3
answers
7k
views
Set of Positive Definite matrices with determinant > 1 forms a convex set
While reading a paper An Arithmetic Proof of John’s Ellipsoid Theorem by Gruber and Schuster, I have a question on their proof.
Consider an $n\times n$ real symmetric and positive definite matrix $\...
