All Questions
Tagged with matrices matrix-inverse
83 questions
7
votes
1
answer
488
views
Invertibility of a matrix defined using inner product
Let $n,m \geq 1$. We fix $n$ distinct vectors $x_1, ... , x_n \in \mathbb{R}^m$. We define $A \in \mathbb{R}^{n\times n}$ as
\begin{equation}
A_{ij} = x_i^T \left(n x_j - \sum_{1 \leq k \leq n} x_k \...
- 2,306
8
votes
1
answer
361
views
Invertible matrix with group ring coefficient
Before asking the question I do need
some notations.
$G$ a (torsion-free) group, $\mathbb{Z}^{´}=\mathbb{Z}[\frac{1}{2}]$
$R:= \mathbb{Z}[G]$, $R^{´}=\mathbb{Z}^{´}[G]$ group rings.
$Mat_{n}(R)$ the ...
- 223
0
votes
1
answer
127
views
Under what conditions does $x^TA^{-1}y> 0$ hold? $A$ is a symmetric positive definite matrix,$A\in \mathbb{R}^{n\times n}_+, x,y\in \mathbb{R}^{n}_+$
This is a tricky problem I encountered in my research. $A\in \mathbb{R}^{n\times n}_+, x,y\in \mathbb{R}^{n}_+$, i.e. $\forall 1\leq i \leq n, 1 \leq j\leq n, A(i, j)>0, x(i), y(i)>0$.
As known, ...
- 27
0
votes
1
answer
127
views
update rule for the inverse after a rank-1 update plus scaled identity
Is there an update rule for $$\left(\tilde{X}^T\tilde{X}+\alpha\cdot I\right)^{-1}$$ with $\tilde{X}=[X\;\; a]$ as a function of $A\triangleq (X^TX)^{-1}$, $X$ and $a$?
I know that when $\alpha=0$ we ...
- 503
4
votes
2
answers
203
views
Results of invertibility of a matrix involving the Szego kernel
In the context of reproducing kernel Hilbert spaces, the Szego kernel is the function $k(z_i,z_j)=\frac{1}{1-z_j\overline{z_j}}$.
Given $2n$ points $\{z_1,\ldots,z_n\},\{w_1,\ldots,w_n\}\in\mathbb{D}\...
- 167
0
votes
0
answers
35
views
What is the impact of individual estimate on each other in matrix inversion?
I am looking to understand the impact of each estimate on each other in matrix inversion.
Lets say I have a vector $A = \left[a_1, a_2 \right]^T$ of size $2 \times 1$ and $a_1$ and $a_2$ are related ...
- 1
1
vote
1
answer
345
views
Solvability of $A X B=C$ with $X=X^\mathrm{T}$
I am studying symmetric solutions to the complex matrix equation
\begin{equation}
A X B=C,
\end{equation}
where $A$, $B$, and $C$ are $m\times n$, $n \times k$, and $m \times k$ complex matrices, ...
- 61
2
votes
0
answers
146
views
What are the name and inverse of an interesting integer matrix?
It is practicable to compute the matrix inverses
\begin{align*}
\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
1 & 2 & 2^2 \\
\end{pmatrix}^{-1}
&=\begin{pmatrix}
1 & 0 &...
- 1,091
2
votes
0
answers
137
views
Decompose a rational matrix as an integer matrix and an inverse of integer matrix
Suppose we have a non-singular rational matrix $Q$, consider the the $\mathbb{Z}$-span of the columns of $Q$ and $Q^{-1}$, denote it as $H = {\rm Span}_{\mathbb Z} \{ Q(\mathbb Z^{n}), Q^{-1}(\...
- 823
3
votes
1
answer
342
views
Inverting a matrix using the Matrix logarithm
This is probably going to lead nowhere, but maybe it be possible to use the matrix logarithm to invert matrices?
For positive definite matrices, we have that the logarithm exists and
$$
\log(A^{-1})= -...
- 385
3
votes
1
answer
332
views
Complexity of inverting and multiplying against a symmetric Toeplitz matrix with two repeated entries
I know that the computational complexity of inverting a general $n \times n$ matrix $A$ is $O(n^{2.373})$ and multiplying it against an $n \times m$ matrix is $O(n^2m)$. Moreover, I've seen that ...
- 91
1
vote
0
answers
95
views
Algorithm for efficiently calculating $(A+\sum_{i=1}^n B_i)^{-1}$ where $A^{-1}\in\mathbb S^n_+$ is known and $B_i$ are sparse matrices
Let $A\in\mathbb R^{n\times n}$ be a symmetric positive-definite matrix and $A^{-1}$ is already known. Now I want to compute the matrix $(A+\sum_{i=1}^n B_i)^{-1}$ where each $B_i$ is a sparse ...
- 601
2
votes
2
answers
185
views
Orthonormal solution of overdetermined linear equations
I have a two matrices $A$ and $B$ in $\mathbb{R}^{m \times n }$ ($m \gg $ n) such that there exists an orthonormal matrix $X \in \mathbb{R}^{n \times n }$, such that:
$$AX = B$$
Given that $X$ is ...
- 123
2
votes
2
answers
272
views
Full-rank matrix
I have a sparse square matrix and want to see if it is full rank (so that I can apply the implicit function theorem).
$$\left[\begin{array}{cccccccccc}
0 & 1 & 1 & 1 & 0 & 0 & ...
- 188
2
votes
1
answer
231
views
Trace inverse of random PSD matrix?
Consider a random matrix $A \in \mathbb{R}^{m\times n}$ with i.i.d. entries, with mean zero and variance 1 and $m <n $. I am interested in the expectation of $$E_{A}(\mathrm{Tr}( (A^T A + \lambda \...
- 25
-2
votes
1
answer
262
views
Proving 2 matrices have the same trace [closed]
I found a problem in my textbook and I have tried solving it, but I had no succes. The problem is:
Let $A$ and $B$ be $n \times n$ matrices with complex number entries. Given that $AB−BA$ is ...
- 331
1
vote
1
answer
252
views
Condition on the probabilities for the $J\times J$ matrix $[ \Pr(X=j \mid Y=k) ]$ to be invertible
$\DeclareMathOperator\Pr{P}\newcommand\cPr[2]{\Pr(#1 \mid #2)}$I have a $J \times J$ matrix:
$$
M:= \begin{bmatrix}
\cPr{X=1}{Y=1} & \cPr{X=2}{Y = 1} & \cdots & \cPr{X=J}{Y = 1} \\
\cPr{X=...
- 151
0
votes
1
answer
138
views
Does there exist a function $f(X)$ with the following gradient $\mathrm{Tr}[(I-X)^{-1}]\cdot g(X)$?
Let $f: \mathbb{R}^{n\times n} \to \mathbb{R}$ be a function that receives a square matrix and spits out a scalar. Does there exist a function $f$ such that the gradient $\nabla_Xf(X) = \mathrm{Tr}[(...
- 59
0
votes
1
answer
155
views
Product of matrices equal identity
I need to solve the following equation for the matrix $P \in\mathbb{R}^{r\times d}:$
$$
((PAP^\top)^{-1} P S P^\top (PAP^\top)^{-1})^2 = I_r,
$$
where $S$ is a symmetric $d\times d$ matrix, $A$ is a ...
- 245
2
votes
2
answers
235
views
When is $(I - X)^{-\top} \circ X = 0$?
I am currently looking at the following expression $(I - X)^{-\top} \circ X = 0$, where $\circ$ is the Hadamard product, $\top$ is the transpose, $I$ is the identity, and $X$ is non-negative and ...
- 59
2
votes
1
answer
137
views
Existence of matrices with some invertibility properties
Prove that there exists five matrices $B_i \in \mathbb{F}_2^{5\times 10}$, $i\in \{1,2,3,4,5\}$, such that any two $B_i$'s form an invertible matrix in $\mathbb{F}_2^{10\times 10}$.
I am interested ...
user83947
3
votes
1
answer
428
views
Minimum upper bound for sum of the entries of the inverse covariance matrix
Let $x \in \mathbb{R}^n$ and $k$ is RBF kernel
$$k(x, x') := \exp \left(-\frac{\|x-x'\|^2}{2\sigma^2}\right)$$
and let $\mathbf{K}$ be the following $n \times n$ covariance matrix
$$\mathbf{K} = \...
5
votes
2
answers
730
views
Do any two hermitian matrices A and B commute with the support of their commutator?
Let $A$ and $B$ be Hermitian matrices. Let $[A,B] = AB - BA$ be their commutator and let $[A,B]^+$ be the Moore-Penrose pseudoinverse of $[A,B]$.
Is it then true that $A$ and $B$ both commute with the ...
- 1,947
2
votes
1
answer
438
views
Mistake in Karl Pearson's 1900 paper introducing the chi-squared distribution
Background
I'm reading Karl Pearson's 1900 paper titled:
On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be ...
- 41
2
votes
1
answer
841
views
Matrix derivative w.r.t. a general inverse form: $(A^TA)^{-1/2}D(A^TA)^{-1/2}$
I want to find derivative of matrix $(A^TA)^{-1/2}D(A^TA)^{-1/2}$ w.r.t. $A_{ij}$ where D is a diagonal matrix. Alternatively, it is okay too to have
$$\frac{\partial}{\partial A_{ij}} a^T(A^TA)^{-1/2}...
- 519
5
votes
2
answers
973
views
Sufficient conditions for invertibility of a block tridiagonal matrix
Let $M_n \in \mathbb{R}^{N \times N}$ be a block-tridiagonal matrix:
$$M_n = \begin{bmatrix} B_1 & C_1 & 0 & 0 & \cdots & 0 \\ A_1 & B_2 & C_2 & 0 & \cdots & 0 \...
- 397
2
votes
1
answer
196
views
Closed form for the inverse of a special transition matrix
Let $b\in\mathbf{R}^n$ be fixed, and let $A\in\mathcal{M}_{n\times n}(\mathbf{R})$ be given but otherwise arbitrary. Let $a_1,\ldots,a_n$ denote the coefficients of the characteristic polynomial of $A$...
- 309
2
votes
1
answer
841
views
Complexity of pseudoinverse of a low-rank matrix
I have a large matrix $\mathbf{A}\in \mathbb{C}^{m\times n}$ with very low rank $r$, I find that the general complexity of finding its pseudoinverse is $\mathcal{O}(\max(m,n)^3)$, this is too high. ...
- 121
32
votes
1
answer
5k
views
Inverting lower triangular matrix in time $n^2$
I have a lower $n\times n$ triangular matrix called $A$ and I want to get $A^{-1}$ solved in $O(n^2)$. How can I do it?
I tried using a method called "forward substitution", but the ...
- 303
9
votes
3
answers
2k
views
How to calculate inverse of sum of two Kronecker products with specific form efficiently?
I have a matrix with specific form of $A\otimes I + B\otimes J$ where $A$ and $B$ are general dense matrices, $n\times n$. $I$ is an $m\times m$ identity matrix. $J$ is a $m \times m$ dense matrix ...
- 91
5
votes
1
answer
438
views
Inverse of a Cauchy-like matrix
Consider $n\times n$ symmetric Cauchy-like matrix $M$ with elements $(M_{ij})_{i,j=1}^{n}$ given by
$$M_{ij} = \frac{1}{(n-i)!(n-j)!(2n-i-j+1)} = \displaystyle\int_{0}^{1}\frac{x^{n-i}}{(n-i)!} \frac{...
- 1,538
3
votes
1
answer
1k
views
Inverse of a larger matrix where the inverse of the submatrix is known
Let $A, A^{-1} \in \mathbb{R}^{n \times n}$ be known matrices. Suppose we have an invertible matrix $B \in \mathbb{R}^{(n+1) \times (n+1)}$ of the following form:
$$B = \begin{bmatrix}
A & ...
1
vote
1
answer
245
views
Low-complexity method for sub-matrix inversion
Assume that $\mathbf{A}$ be an $N\times N$ matrix. We know that the complexity of the computation of matrix inversion is $\mathcal{O}(N^3)$. Let define $\mathbf{D}=\mathbf{A}^{-1}$. Now, assume that $\...
- 287
2
votes
0
answers
300
views
Bound for the inverse of a summation of rank-1 matrices
Given vectors $x_1,\dots,x_T \in R^d$ satisfying $\|x_i\|_2 = 1$, define $A_0 = I$ and $A_t = I + \sum_{i=1}^tx_ix_i^\top$ for $t \geq 1$. We are interested in the following quantity:
\begin{align}
S_{...
- 21
7
votes
1
answer
3k
views
What are known properties of matrices where off-diagonal elements are 1?
Consider a matrix where the diagonal entries are anything but the off-diagonal entries are all one. I was able to find a formula for the determinant of this matrix, but what are other known properties?...
- 277
3
votes
0
answers
75
views
Solutions to a special confluent Vandermonde system
Consider the polynomial $P(X) =\prod_{i=1}^k (X-x_i)^s$ and let $M$ be the corresponding confluent Vandermonde matrix. Concretely, here is what I mean by that. Define
$$
M^{(0)} = \begin{pmatrix}
1 &...
- 613
3
votes
2
answers
375
views
Inequality for 0-1 matrices
Given an $n \times n$-matrix $A$ with entries only $0$ or $1$ and determinant equal to $\pm 1$. Define the magnitude $M_A$ of $A$ as the sum of all entries of the inverse of $A$.
Question 0: Do we ...
- 26.5k
1
vote
1
answer
499
views
A closed-form expression for the inverse of a block-matrix
Let $\bf A$ be an $n \times n$ non-singular matrix over $\mathbb{F}$.
Let $x$ be a non-zero element of $\mathbb{F}$.
Suppose that ${\bf 1}_{n}$ is a symbol for the all-one vector of length $n$ ...
- 211
3
votes
0
answers
231
views
Singularity of symmetric block matrix with singular diagonal blocks
One can show that the following statement holds:
Given symmetric matrix $A \in \Re^{n \times n}$ and tall matrix $B \in \Re^{n \times p}$ with full column rank,
$$\begin{bmatrix}A & B \\ B^T &...
- 73
3
votes
1
answer
454
views
Difference of pseudoinverse bound under assumptions
This seems like a standard problem, but unable to find a solution online.
Suppose we have two singular PSD matrices A and B with the following assumptions:
$ 0 < x \leq ||A|| \leq y$
$ 0 < ||...
- 33
1
vote
2
answers
143
views
Controllability Gramian asymptotics for small times
Set-up. Consider the following linear controlled system
$$
\dot{y}(t) = A y(t) + B u (t), \ \ t \in [0,T], \ \ \ \ \ \ \ \ \ \ (1)
$$
where $y$ is the state of the system, $y(t) \in R ^n$, $A \in R ...
- 724
7
votes
1
answer
856
views
Trace of inverse of random positive-definite matrix in high dimension?
Consider a random matrix $A \in \mathbb{R}^{n\times n}$ with i.i.d. entries, with symmetric law and finite variance. I am curious about the behavior of $$\mathrm{Tr}( (A^T A + \lambda \mathrm{Id})^{-1}...
- 2,306
1
vote
0
answers
111
views
Angle inequality for inverse of PD diagonal matrix
I have two diagonal, positive definite matrices $A$ and $B$, and I have that the angle between $Ax$ and $x$ is smaller than that of $Bx$ and $x$:
$$\frac{x^T A x}{\|Ax\|_2} \geq \frac{x^T B x}{\|Bx\|...
- 269
5
votes
1
answer
368
views
$(AB)^+\approx B^+A^+$ for $B$ "fat" enough?
Let $A\in\mathbb{R}^{r\times m}$ be a matrix of full row rank, and let $\cdot^+$ denote the Moore-Penrose inverse.
Consider a sequence of matrices $\{B_n\}_{n>1}$, $B_n\in\mathbb{R}^{m\times n}$, ...
- 2,712
7
votes
1
answer
2k
views
Determinant and Inverse of a Toeplitz matrix
Let $T(n,k)$ be a $n \times n$ symmetric Toeplitz matrix, where all the entries of first $k$ super-diagonal (and sub-diagonal), last $k-1$ super-diagonal (and sub-diagonal) are ones, and rest of the ...
- 640
1
vote
0
answers
319
views
Derivative of complex matrix pseudo inverse with respect to real and imaginary components
I have a complex non-square matrix $\mathbf{Y}\in\mathbb{C}^{n \times m}$ whose inverse I compute using the Moore-Penrose pseudo inverse, $\mathbf{Z}=\mathbf{Y^+}$.
I am interested in evaluating the ...
2
votes
3
answers
550
views
Inverse of matrix $D + ADA^T$
Let $D$ be an arbitrary diagonal matrix and let $A$ be an orthogonal matrix ($A'A = AA' = I$). How to compute the following matrix inverse efficiently?
$$(D + ADA^T)^{-1}$$
Hints or references are ...
- 89
4
votes
1
answer
3k
views
Approximating the expectation of a matrix inverse
Let
$$R := A \Lambda^{-1} A^H + \frac{1}{\gamma} I_n$$
where $A$ is a given $n \times m$ matrix (where $m \gg n$),
$$\Lambda := \mbox{diag} \big( \lambda_1, \lambda_2, \dots, \lambda_m \big)$$
...
- 67
11
votes
2
answers
2k
views
Inverse of a small submatrix
Let $A$ be a large matrix (say, $1000 \times 1000$), and let $\mathcal I = \{2,3,5\}$ be a set of row/column indices. Let $(A^{-1})_{\cal I \times I}$ denote the submatrix of $A^{-1}$ that consists of ...
- 241
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 $...
- 31