Questions tagged [numerical-linear-algebra]

Questions on the various algorithms used in linear algebra computations (matrix computations).

2,237 questions
58k views

Distance/Similarity between two matrices

I'm in the process of writing an application which identifies the closest matrix from a set of square matrices $M$ to a given square matrix $A$. The closest can be defined as the most similar. I ...
22k views

6k views

What is the practical impact of a matrix's condition number?

Let's say I am trying to solve a square linear system $Ax = b$ for whatever reason. A perturbation $\delta b$ in $b$ will lead to a perturbation $\delta x$ in $x$, whose relative norm is bounded by ...
223 views

Determinant of $5 \times 5$ Boolean matrix

Consider the set of $5 \times 5$ matrices with $10$ entries equal to $1$ and the other $15$ entries equal to $0$. I would like to know how many such matrices have nonzero determinant. Is there a way ...
947 views

3k views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and $b$...
5k views

2k views

I'm looking for a numerically stable method for computing the angle between two 3D vectors. Which of the following methods ought to be preferred? Method 1: $$u\times v = ||u||~||v|| \sin(\theta) \... 1answer 1k views Fast algorithm for approximating Eigenvalue distribution of large sparse matrix I am interested in the eigenvalue distribution of a huge 2^{16}x2^{16} Hermitian sparse matrix with spectrum contained in [-1,1]. That is I don't need to know all eigenvalues exactly, but rather ... 1answer 899 views Sum of idempotent matrices is Identity [Ciarlet, Problem 1.1-10] Let A_k, 1 \leq k\leq m, be matrices of order n satisfaying$$\sum_{k=1}^mA_k\ =\ I.$$Show that the following conditions are equivalent. A_k = (A_k)^2, ... 2answers 8k views matrix similarity upper triangular matrix How to show: Any matrix A with real or complex entries is similar to an upper triangular matrix M whose diagonal entries are the eigenvalue of A. Thank you! 5answers 3k views Is there a faster way to calculate a few diagonal elements of the inverse of a huge symmetric positive definite matrix? I asked this on SO first, but decided to move the math part of my question here. Consider a p \times p symmetric and positive definite matrix \bf A (p=70000, i.e. \bf A is roughly 40 GB using 8-... 3answers 975 views Matlab code to compute the smallest nonzero singular value of the matrix without using SVD I want to compute the smallest nonzero singular value of the matrix A, which is defined as follows. Let B = rand(500, 250), A = B*B^t, where t denotes the transpose of the matrix. I found ... 2answers 2k views Inverse of the sum of a symmetric and diagonal matrices I have two matrices A and B with quite a few notable properties. They are both square. They are both symmetric. They are the same size. A has 1's along the diagonal and real numbers in (0 ... 3answers 2k views What are the real life applications of quadratic forms? What are the real life applications of quadratic forms? I have used them to sketch conics but are there any other applications? 1answer 2k views What would be a good method for finding the submatrix with the largest sum? This question is from an ongoing contest which ends in 4 days. It is this problem from the October Challenge. Given:A Matrix (Not necessarily square) filled with negative and positive integers.What ... 1answer 169 views Vandermonde matrices nullspaces and notation I'm following the book Mimetic Discretization Methods by Castillo and Miranda, reading the page 209-211, it states the following: Let V(m;G) be a Vandermonde matrix, of order m with generator G =... 1answer 242 views Generate arbitrary numerically invertable matrix I'm designing a unit-test for a matrix inversion function. Currently I make a random matrix as a test case by generating its elements with random numbers uniformly distributed in [0,1). If I ... 2answers 296 views What new insights does numerical analysis give on linear algebra? I know linear algebra decently well, but I've never taken a numerical analysis course. However, I've heard that it provides a good intuition for the subject. Assuming that I'm already familiar with ... 1answer 5k views What is the time complexity of conjugate gradient method? I have been trying to figure out the time complexity of the conjugate gradient method. I have to solve a system of linear equations given by$$Ax=b$$where A is a sparse, symmetric, positive ... 1answer 275 views Why would (A^{\text T}A+\lambda I)^{-1}A^{\text T} be close to A^{\dagger} when A is with rank deficiency? In many applications that is not with high requirements, it is common to use (A^{\text T}A+\lambda I)^{-1}A^{\text T} or A^{\text T}(AA^{\text T}+\lambda I)^{-1} (\lambda is small) to ... 1answer 802 views Precision and performance of Euclidean distance The usual formula for euclidean distance that everybody uses is$$d(x,y):=\sqrt{\sum (x_i - y_i)^2}$$Now as far as I know, the sum-of-squares usually come with some problems wrt. numerical ... 1answer 2k views Properties shared by similar and unitary similar matrices. We know that matrices A and B are similar if there exists an invertible matrix P such that A=PBP^{-1} and they are unitarily similar if P is unitary (PP^*=P^*P=I). I want to know : What ... 1answer 654 views Is Householder orthogonalization/QR practicable for non-Euclidean inner products? The question Is there a variant of the Householder QR algorithm to orthonormalize a set of vectors with respect to an inner product if no orthonormal basis is known a priori? Background Let's ... 1answer 168 views Compute a diagonalizable matrix close in matrix exponential It is known that for any matrix A, one can perturb A slightly so that the resulting A(\epsilon) is diagonalizable. I am wondering whether for any matrix A, \epsilon>0, there is an ... 1answer 175 views Singularity of a positive linear combination of rank one matrices Given a set of rank one matrices A_1,..,A_n, we need to find out if there exists x \in \mathbb R^n with x\gg 0 (i.e, positive) such that$$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + x_n A_n $$... 1answer 917 views Floating point arithmetic operations when row reducing matrices A numerical note in my linear algebra text states the following: "In general, the forward phase of row reduction takes much longer than the backward phase. An algorithm for solving a system is usually ... 1answer 2k views What is the Moore-Penrose pseudoinverse for scaled linear regression? The matrix equation for linear regression is:$$ \vec{y} = X\vec{\beta}+\vec{\epsilon} $$The Least Square Error solution of this forms the normal equations:$$ ({\bf{X}}^T \bf{X}) \vec{\beta}= {\bf{...
What is the name of the following matrix? \begin{pmatrix} a & b & 0 \\ c & d & 0 \\ 0 & a & b\\ 0& c& d& \\ b & 0 & a \\ d & 0 & c\end{...
I'm working through the book Numerical Linear Algebra by Trefethen and Bau. In Lecture 27 (and exercise 27.5), the following claim is made about the inverse iteration algorithm: Let $A$ be a real, ...