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 ...
Noam D. Elkies's user avatar
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 &...
WhatsUp's user avatar
  • 3,232
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=...
Pietro Majer's user avatar
  • 56.6k
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 ...
Suvrit's user avatar
  • 28.4k
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 &...
Ehud Meir's user avatar
  • 4,979
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 ...
Dan Piponi's user avatar
  • 8,116
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 $$...
Denis Serre's user avatar
  • 51.6k
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$ ...
Carlo Beenakker's user avatar
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 ...
Federico Poloni's user avatar
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 ...
thedude's user avatar
  • 1,417
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 ...
G Cab's user avatar
  • 208
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 ...
T. Amdeberhan's user avatar
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}...
Alex Gavrilov's user avatar
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$, ...
Geoff Robinson's user avatar
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} \...
Carlo Beenakker's user avatar
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 (\...
Brendan McKay's user avatar
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-...
Henricus V.'s user avatar
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^...
Samrat Mukhopadhyay's user avatar
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 ...
Yuval Peres's user avatar
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....
Fred Hucht's user avatar
  • 2,705
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=...
Christian Remling's user avatar
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) ...
Christopher Gallegos's user avatar
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{...
user147084's user avatar
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\...
Samrat Mukhopadhyay's user avatar
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 ...
Federico Poloni's user avatar
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 ...
Carlo Beenakker's user avatar
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)^{-...
Denis Serre's user avatar
  • 51.6k
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 ...
Noam D. Elkies's user avatar
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)
Carlo Beenakker's user avatar

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