91
votes

Accepted

### Inverting lower triangular matrix in time $n^2$

No such method is known at present.
If one could invert lower triangular $n \times n$ matrices in time $O(n^2)$
then one could multiply $N \times N$ matrices in time $O(N^2)$.
Indeed let $n=3N$ and ...

20
votes

Accepted

### Inverse of special upper triangular matrix

Let $A$ be the nilpotent matrix $$\begin{pmatrix}0 & 1 & 1 & \cdots & 1 \\ & 0 & 1 & \cdots & 1 \\ & & \cdots & \cdots & \cdots \\ & & & 0 &...

15
votes

### Find the inverse of a matrix that is very similar to the Hilbert matrix

As observed in comments, the problem is equivalent to finding the inverse of the matrices $$H_\lambda:=\Big[{1\over i+j+\lambda}\Big]_{1\le i\le m\atop 1\le j\le m},$$
for $\lambda=-1/2$ and $\lambda=...

11
votes

### Inverse of a small submatrix

One way to go about this is as follows:
For $i,j \in \mathcal{I}$ Compute $e_i^TA^{-1}e_j$ by using the approach based on Gaussian quadrature; see for instance, a precise algorithm and analysis in ...

10
votes

Accepted

### minimum-maximum entries matrix

Let us write $$a_r=\frac{x_{r+1}}{x_r}$$ for $r=1\cdots n$.
We can then write the matrix $M(n)$ in the form
$$\begin{pmatrix} 1 & a_1 & a_1a_2& \cdots & a_1a_2\cdots a_{n-1} \\ a_1 &...

8
votes

### Should the formula for the inverse of a 2x2 matrix be obvious?

For $\mathbf{A}$ near zero we have
$$
(1-\mathbf{A})^{-1}\approx 1+\mathbf{A}
$$
so it has to negate the off-diagonals.
(If you want to get all fancy about it you could notice that we use $\exp$ to ...

8
votes

### Relation between eigenvalues of $A$ and $A^TA$?

Let $\lambda_1,\ldots,\lambda_n$ be the eigenvalues of $A$ and $s_1,\ldots,s_n$ be those of $\sqrt{A^*A}$, ordered by
$$|\lambda_1|\ge\cdots\ge|\lambda_n|,\qquad s_1\ge\cdots\ge s_n.$$
Then it holds
$$...

7
votes

Accepted

### Trace of inverse of random positive-definite matrix in high dimension?

If the elements of the $n\times n$ matrix $A$ are independent identically distributed random variables with mean 0 and variance $\sigma^2$, the $n$ eigenvalues $x_i$ of $A^{\rm T}A$ have for large $n$ ...

7
votes

Accepted

### Inverting a matrix using the Matrix logarithm

Numerically, inverting a matrix by computing matrix exponentials and logarithms doesn't really work well, because (1) typically methods to compute matrix exponentials and logarithms are much more ...

6
votes

### Relation between eigenvalues of $A$ and $A^TA$?

A simple relation between singular values and eigenvalues does not exist in general, as far as I know.
This is an old question, e.g.
A. Horn, On the eigenvalues of a matrix with prescribed singular ...

6
votes

Accepted

### Inverse of a matrix with binomial entries

Let's refer everything to square matrices indexed from $0$ to $h$, that I will denote as
$$
{\bf M}_{\,h} = \left\| {\;f(n,m)\;} \right\|_{\,h}
$$
with $n$ being the row index and $m$ the column ...

6
votes

Accepted

### Find the inverse of a matrix that is very similar to the Hilbert matrix

We present a generalization and also give an explicit solution.
If $M$ is the $n\times n$ matrix
$$M=\left[\frac{1+(-1)^{i+j}}{x_i-y_j}\right]_{i,j=1}^n$$
then the inverse matrix $K:=M^{-1}$ has ...

6
votes

### Inverse of matrix $D + ADA^T$

To begin with, the matrix in question can well be degenerate, consider for example
\begin{equation*}
D=\left(
\begin{array}{cc}
1 & 0 \\
0 & -1
\end{array}\right),
A=\left(
\begin{array}{cc}...

6
votes

Accepted

### What are known properties of matrices where off-diagonal elements are 1?

Such a matriix has the form $J +D,$ where $D$ is a diagonal matrix, and $J$ is a square matrix with all entries $1$. One small remark is that if $D$ has two of its diagonal entries equal to $\lambda$, ...

6
votes

### Computation to differentiate a determinant

The condition $\lambda+\mu_1>0$ ensures that $M(\lambda)=A+\lambda $ is invertible, and then one can use Jacobi's formula
$$\frac{d}{d\lambda} \det M(\lambda) = \det M(\lambda) \operatorname{tr} \...

6
votes

Accepted

### Computation to differentiate a determinant

The eigenvalues of $A+\lambda$ are $\{\mu_j+\lambda\}$ which are positive by assumption. So
$$\frac{d}{d\lambda} \log\det(A+\lambda)
= \frac{d}{d\lambda} \sum_j \log (\lambda+\mu_j)
= \sum_j (\...

5
votes

Accepted

### Deriving inverse of Hilbert matrix

(Note: The matrix elements are indexed from $0$. To avoid confusion, I will not index into a matrix without brackets)
Here is a naive approach to this problem, without hindsight of the already-...

5
votes

### Inverse of particular lower triangular matrix

One observation:
$$A = I+L,$$ where $L$ is a lower triangular matrix with $0$ in the diagonals. This matrix $L$ can be seen to satisfy $L^n=0$, and $L^j\ne 0,\ 1\le j\le n-1$. Thus, one can write $$A^...

5
votes

Accepted

### If $\Vert A-B\Vert_{op}\leq \varepsilon$ then $A^{-1}$ and $B^{-1}$ are uniformly close

$A^{-1}-B^{-1}=B^{-1}(B-A)A^{-1}$ so
$\|A^{-1}-B^{-1}\| \le \delta_0^{-2} \epsilon $. This is the best possible bound in terms of the given parameters, as you can see by considering 2 by 2 diagonal ...

5
votes

Accepted

### Full-rank matrix

OK, let's call the block matrix above $M$. First eliminate $N$ by a substitution $c\mapsto d N$. Then substitute $z_i \mapsto d y_i$ to eliminate $d$. Then you can construct the Schur complement w.r.t....

5
votes

Accepted

### Results of invertibility of a matrix involving the Szego kernel

Expand the determinant $D=\det k(x_j,y_k)$ along the first row. This shows that as a function of $x=x_1$, it is of the form
$$
D(x) = \sum_{j=1}^n \frac{c_j}{1-y_j x} ,
$$
with $c_j$ independent of $x=...

4
votes

### Should the formula for the inverse of a 2x2 matrix be obvious?

There's lots of great answers here, but they may be inaccessible to students first encountering this material, so here's my intuition for the 2x2 inverse at an undergraduate (maybe even high-school) ...

4
votes

### Invertibility of the Schur Complement

Yes, if you take the determinants, you obtain with
$$\operatorname{det}(M)=\operatorname{det}(M/ D)\cdot\operatorname{det}(D)
$$
therefore if $\operatorname{det}(M)$ is non-zero then $\operatorname{...

4
votes

Accepted

### Inverting (via Taylor expansion) a sum of (rank-deficient) skew-symmetric matrix and (rank-deficient) Diagonal matrix

Just an idea.
I think the best way to start is to expand on the structure of the matrices $D, C$. For example, $D$ can be readily seen to be expressible in the form $$\alpha M_1\otimes I_2=\alpha\...

4
votes

### What is the most accurate and efficient method of finding an inverse of a hessian matrix?

This would probably get better answers on [scicomp.se]. Anyway:
If you value accuracy over efficiency, using a QR factorization gives a backward stable algorithm, i.e., it guarantees that your ...

4
votes

### Inverse of a small submatrix

Let me denote $B=A^{-1}$. The question is how to efficiently compute the inverse of a submatrix of $B$ given the fact that the inverse of the full matrix $B$ is known (since $B^{-1}=A$). An efficient ...

4
votes

Accepted

### A closed-form expression for the inverse of a block-matrix

Say that
$$B^{-1}=:\begin{pmatrix} b & X^T \\ Y & M \end{pmatrix}.$$
Then using Schur's complement formula (thanks to Nathaniel), $b=(x-{\bf1}^TA^{-1}{\bf1})^{-1}$ and $M=(A-x^{-1}{\bf11}^T)^{-...

4
votes

### Inequality for 0-1 matrices

The "magnitude" can grow exponentially with $n$,
even when $A$ is triangular (and thus has all-$1$ diagonal)
with no more than three $1$'s in each row and column.
Indeed suppose $A_{ij} = 1$ if and ...

4
votes

### Condition number for matrix of eigenvectors of a diagonalizable matrix

See: An upper bound for the spectral condition number of a diagonalizable matrix (1997)

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

matrix-inverse × 140matrices × 79

linear-algebra × 74

matrix-analysis × 22

matrix-theory × 15

random-matrices × 11

determinants × 8

numerical-linear-algebra × 8

pr.probability × 7

eigenvalues × 7

block-matrices × 7

matrix-equations × 6

ra.rings-and-algebras × 5

na.numerical-analysis × 5

convex-optimization × 5

traces × 5

fa.functional-analysis × 4

st.statistics × 4

algorithms × 4

asymptotics × 4

orthogonal-matrices × 4

inverse-problems × 4

reference-request × 3

graph-theory × 3

inequalities × 3