Skip to main content
54 votes
Accepted

Determinant of large matrices: there's GOTTA be a faster way

No, this is not the way that any (sane) person would compute a determinant. This is not even the way a computer would calculate a determinant! It requires a sum over $n!$ terms, which quickly becomes ...
Joppy's user avatar
  • 13.1k
47 votes

What does QR decomposition have to do with least squares method?

Overview Difficulties in understanding why we use QR-decompositions to find linear least squares could arise either because the mathematics is poorly motivated (why would we choose this method?) or ...
Richard's user avatar
  • 1,366
18 votes
Accepted

What is the most efficient way to find the inverse of large matrix?

Let's solve $Ax = b$. The first equation in this linear system tells us that $-x_0 + a_0 x_n = b_0$, or $$ x_0 = a_0 x_n - b_0. $$ The second equation tells us that \begin{align} & x_0 - x_1 + ...
littleO's user avatar
  • 52.4k
17 votes
Accepted

How to inverse a block diagonal matrix?

Block diagonal matrices can be inverted block by block. See also [*]. In your example: $$\begin{bmatrix} 40 & 0 & 0 & 0 \\ 0 & 80 & 100 & 0 \\ 0 & 40 & 120 & 0 \\ 0 ...
Florian's user avatar
  • 2,630
16 votes

Numerically stable method for angle between 3D vectors

Short answer: Method 2 is better for small angles. Use this slight rearrangement: $$ \theta = 2~atan2(||~||v||u - ||u||v~||,~||~||v||u + ||u||v~||) $$ This formula comes from W. Kahan's advice in his ...
D0SBoots's user avatar
  • 475
14 votes
Accepted

Why is the condition number of a matrix given by these eigenvalues?

In the book, the condition number refers to the matrix $A \in \mathbb{R}^{n \times n}$, not the function as you stated in the question. The condition number of a matrix $A$ is defined as $$ \kappa(A)...
durdi's user avatar
  • 763
14 votes

Why { $z-x-y=0$ , $z-2x=0$ , $2x+y-3z=0$ } cannot be solved this way?

Your friend used just two equations, which (since they were linearly independent) is enough to limit the solution space to one dimension. The correct conclusion is not that $\langle x,y,z\rangle = \...
David K's user avatar
  • 99.5k
13 votes

block matrix multiplication

It is always suspect with a very late answer to a popular question, but I came here looking for what a compatible block partitioning is and did not find it: For $\mathbf{AB}$ to work by blocks the ...
einar's user avatar
  • 241
12 votes

What is a big condition number for a matrix?

You can view a solver as a black box which maps the input (in your case, the right-hand side vector) into the output (in your case the solution). The condition number connects the relative error of ...
Carl Christian's user avatar
11 votes

Linear Algebra: If $A^3 = I$, does $A$ have to be $I$?

An example of a matrix $A$ such that $A^3 = I$ is $$ A = \left( \begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{matrix} \right) $$
Bolton Bailey's user avatar
11 votes

Linear Algebra: If $A^3 = I$, does $A$ have to be $I$?

Consider the matrix \begin{align} A= \begin{pmatrix} \cos \frac{2\pi}{3} & -\sin\frac{2\pi}{3}\\ \sin\frac{2\pi}{3} & \cos \frac{2\pi}{3} \end{pmatrix} \end{align}
Jacky Chong's user avatar
  • 25.8k
11 votes

What makes Krylov subspaces so special?

A good way to motivate the use of Krylov subspace methods is the following idea, which is closely related to a derivation of the conjugate gradient method. $\newcommand{\dotp}[2]{\langle #1,#2 \rangle}...
H. Rittich's user avatar
11 votes
Accepted

What does QR decomposition have to do with least squares method?

In the $QR$-decomposition, $Q$ is an orthogonal matrix. One property of these matrices is that they don't change the length of vectors (in the 2 norm). Thus, we have that $$\Vert Ax - b \Vert = \Vert ...
Dirk's user avatar
  • 6,399
11 votes
Accepted

Raise a Matrix to Arbitrary Power

A result can be obtained by direct computation. It can be seen that the first row of $A_k$ is $$(A_k)_{1, j} = 1.$$ Then, the first row of $A_k^{\nu+1}$ is produced by taking partial sums as follows $$...
Pantelis Sopasakis's user avatar
10 votes

LU Decomposition vs. QR Decomposition for similar problems

I recognize that I'm probably far too late for my answer to be of much use to you, but I'll add an answer here for posterity. First, regarding the choice of method: MATLAB has a very clear ...
Vyas's user avatar
  • 357
10 votes
Accepted

Why is solving linear equation more stable than directly computing matrix inverse?

If $x$ is computed by LU factorization, the residual can be bounded by $$ \|b-Ax\|\leq cu\||L||U|\|\|x\|. $$ Assuming for simplicity that $A^{-1}$ is computed exactly and that the only source of error ...
Algebraic Pavel's user avatar
9 votes

The benefit of LU decomposition over explicitly computing the inverse

Let $B * y$ denote matrix multiplication performed in finite precision arithmetics. Let $x_{LU}$ be the solution of $A x = b$ obtained by the LU method, and $x_{inv}$ be the solution computed as $x_{...
Pawel Kowal's user avatar
  • 2,252
9 votes
Accepted

Computationally efficient way to compute projection matrix

I'm going to suggest an indirect method which, while slightly longer, is more accurate. Suppose $A$ is $n\times m$ with $n > m$ has full column rank. As a rule of thumb, you can usually get away ...
eepperly16's user avatar
  • 7,292
8 votes
Accepted

Why not always make a linear system's matrix symmetric?

For a dense, square $A$, cost of forming $A^TA$ is of order $2n^3$, and cost of performing LU factorization is of order $2/3n^3$. Thus, solving $A^TAx = A^Tb$ instead of $Ax=b$ is more expensive. For ...
Pawel Kowal's user avatar
  • 2,252
8 votes
Accepted

What is the difference between ILU(0) and ILU(1)?

I think the best way to explain the ILU decomposition is with pictures. Let $A$ be the band matrix from the 5-point-star of the Finite Difference method \begin{align*} A&=\begin{pmatrix} B_m & ...
P. Siehr's user avatar
  • 3,672
8 votes
Accepted

Perturbation Theory: Approximation of an inverse of a matrix

It is just Taylor expansion: $$\tag{1}(I+\epsilon K)^{-1} = 1-\epsilon K + O(\epsilon^2), $$ so if $H:=\epsilon K$ is small with respect to the identity matrix then you can neglect the quadratic ...
Giuseppe Negro's user avatar
8 votes
Accepted

Proving the Jacobi method converges for diagonally-column dominant matrices

The Jacobi iteration is an example of a stationary iteration $$ x_{n+1} = G x_n + f.$$ By induction we obtain $$ x_n = \sum_{j=0}^n G^j f.$$ In particular, we have $x_n \rightarrow (I-G)^{-1}f$ when, ...
Carl Christian's user avatar
8 votes

Why is the condition number of a matrix given by these eigenvalues?

The book is wrong. The matrix must be normal. Existence of an eigenvalue decomposition is not enough (counter to what they claim on that page). For example, the matrix $$\begin{bmatrix} 1 & 99 \...
Nick Alger's user avatar
8 votes
Accepted

Solving overdetermined system by QR decomposition

The most straightforward way I know is to pass through the normal equations: $$A^T A x = A^T b$$ and substitute in the $QR$ decomposition of $A$ (with the convention $Q \in \mathbb{R}^{m \times n},...
Ian's user avatar
  • 102k
8 votes
Accepted

When solving a linear system, why SVD is preferred over QR to make the solution more stable?

You should check out chapter 3 in Demmel's text. Let me summarize some of the results for dense least-squares, for $A$ an $m\times n$ matrix: $A$ is well-conditioned: In this case, using the normal ...
cmk's user avatar
  • 12.4k
8 votes

What is the most efficient way to find the inverse of large matrix?

Gaussian Elimination should be plenty fast, so perhaps the issue is how you are implementing it. We want to solve $$\begin{bmatrix} -1 & 0 & 0 &\cdots & 0 & a_0\\ 1 & -1 & ...
Ragib Zaman's user avatar
  • 35.2k
8 votes
Accepted

Spectral radius greater than 1

Suppose $\rho(A)\le1$ so $|\lambda_i|\le1$ for all $i$. But the product of eigenvalues is $-1$ i.e. $|\lambda_1||\lambda_2||\lambda_3|=1$. This means that all eigenvalues have unit modulus, and in ...
Shubham Johri's user avatar
8 votes
Accepted

Given $AB$, where $A$ and $B$ are $2×2$ matrices, find $BA-(BA)^{-1}$.

The solution is unique. Hint: Note that $\det(AB)=-1$ so we must also have $\det(BA)=-1$. Then write $BA = \pmatrix{a & b \\ c & d}$ and calculate $BA-(BA)^{-1}$. You realize that the ...
H. H. Rugh's user avatar
  • 35.3k
8 votes
Accepted

Symmetric matrix is positive semidefinite

This is not true. Random counterexample: $$ A=\pmatrix{1&\frac34&0&\frac12\\ \frac34&1&\frac34&0\\ 0&\frac34&1&\frac12\\ \frac12&0&\frac12&1}. $$ $A$ ...
user1551's user avatar
  • 141k

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