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

learn more… | top users | synonyms

1
vote
1answer
20 views

Sparse Matrix or Dense Matrix

My task is to implement the inner product and vector triad forms for a dense $A$ in single and double precision. I have successfully implemented the inner product and vector triad form although, I am ...
2
votes
1answer
30 views

Eigenvalue perturbation theory for $(A^TA)(B^TB)^{-1} + (B^TB)(A^TA)^{-1}$

Let $A, B$ be $n \times n$ matrices with full rank. I'm interested in getting a bound on how the smallest eigenvalue of $S = (A^TA)(B^TB)^{-1} + (B^TB)(A^TA)^{-1}$ changes when I perturb $A$ and $B$. ...
1
vote
1answer
16 views

Order of $LU$ factorisation

Can someone tell me how to calculate the order of a) $LU$ decomposition as well as b)the gaussian elimination of a square matrix $A$? I am at a loss ... Given:: $A$ is a $n\times n$ matrix and ...
2
votes
1answer
12 views

Finding linearly independent columns of a matrix when $m < n$

I need to a maximal set of linearly independent columns of a matrix $A$. I've googled a lot and seen various solutions, but none of them seem to work for me. What I've seen so far is 1.- Using ...
0
votes
1answer
15 views

Efficient Row Sum of Factorized Matrix

I am currently computing the row sums of a reduced rank factored matrix by reconstructing a row subset of the original (approximated) matrix. The matrix was factored using SVD: A -> U, S, V -> U, SxV ...
1
vote
1answer
43 views

Matrix-vector product of a banded matrix

Suppose $A\in\mathbb{R}^{n\times n}$ is a banded matrix, i.e., a matrix with all of its nonzero elements on the main diagonal, i.e., $\alpha_{i,i}\neq 0$, the first superdiagonal, i.e., ...
0
votes
0answers
37 views

A generalized eigenvalue problem

The generalized eigenvalue problem likes this: $\begin{pmatrix} 0 & C_{12}\\ C_{21} & 0 \end{pmatrix} \begin{pmatrix} \xi_1\\ \xi_2 \end{pmatrix}=\rho\begin{pmatrix} C_{11} & 0\\ 0 ...
0
votes
1answer
28 views

Backward Stability Lemma

Lemma-Let $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^n$ with components, $\xi_i$ and $\eta_i$, $1\leq i\leq n$, respectively, that are floating point numbers. Computing the inner product $x^Ty$ on a ...
2
votes
1answer
45 views

In common tongue, what is the differences between sparse and dense matrices?

What are the differences with sparse and dense matrices in practice, so as to offer some insight to new learners on a more intuitive level. Obviously everyone knows about the dictionary definition of ...
1
vote
0answers
30 views

How to add single wavelength discrimination to the Kutulakos & O'Toole paper on a generalized Light Transport Matrix system [closed]

I wish to add single wavelength discrimination to the excellent paper Transport-Aware Imaging, Proceedings of SPIE Vol 9376, 937606 @ 2015 SPIE ,authored by Professor Kiriakos Kutulakos and Ph.D ...
0
votes
2answers
27 views

Find a spd matrix $C \in \mathbb{R}^{n\times n}$ such that $\langle Cv_i,v_j\rangle = \delta_{ij}$

Let $v_1,\ldots,v_n$ be set of eigenvectors of matrix $A \in \mathbb{R}^{n\times n}$. Find a symmetric positive definte matrix $C \in \mathbb{R}^{n\times n}$ such that $\langle Cv_i,v_j\rangle = ...
0
votes
1answer
32 views

$\kappa(B^{-1}A)=\kappa (AB^{-1}) = \frac{\lambda_{max}(B^{-1}A)}{\lambda_{min}(B^{-1}A)}$

Prove or disprove if $A,B$ are symmetric positive definite (s.p.d) matrices then operator 2-norm condition number $\kappa(B^{-1}A)=\kappa (AB^{-1}) = ...
0
votes
2answers
31 views

2-norm of the orthogonal projection

So far, I've deduced that if the rank of A is n, then all the columns of A are linearly independent since A has n columns. As a result, m must be greater than or equal to n. In the case that m = n, ...
1
vote
1answer
25 views

Does matrix norm change under an equivalence transformation? [closed]

Consider $||.||_2$ matrix norm. Let A, B be symmetric matrix, is ||A|| and $||BAB^{-1}||$ equal? Thank you in advance.
0
votes
1answer
36 views

Prove or disprove if $µ_0(Bx, x) ≤ (Ax, x) ≤ µ_1(Bx, x), ∀x ∈ R^n$, then $κ(B^{−1}A) ≤ \frac{µ_1}{µ_0}$

Let $A, B ∈ \mathbb{R}^{n×n}$ symmetric. Show that conditional number $$κ(B^{−1}A) ≤ \frac{µ_1}{µ_0}$$ holds, if $B ∈ \mathbb{R}^{n×n}$ is a symmetric positive definite matrix satisfying $$µ_0(Bx, x) ...
0
votes
0answers
15 views

Hilbert Matrix, Gaussian Elimination with varying pivot strategies, and computation error.

I'm doing a project for my Numerical Analysis class about computational error related to Gaussian elimination, gaussian elimination with partial pivoting, and gaussian elimination with scaled partial ...
2
votes
2answers
58 views

From $Ax=\lambda x$, we have $Ax i = \lambda x i$ , where $i^2=-1$??

Actually I found this problem when I met a question, asking me to prove the eigenvector and eigenvalue of real symmetric matrices are all real. I have already proved the eigenvalue part already, but ...
0
votes
0answers
22 views

Matrix approximation

How to solve numerically for non-negative full-rank matrices $P$ and $E$ with the following constraints? $Y$ is a known non-negative matrix with $G$ rows and $N$ columns, $G > N$ 1) ...
0
votes
2answers
19 views

whether the product of two symmetric matrix with one positive definite is diagonizable

Assume $A$ is symmetric and positive definite, $B$ is symmetric. Proof that $AB$ is diagonalizable and all the eigenvalues are real. I think it is better to write $A=R^TR$ and $B=XDX^{-1}$, but I ...
0
votes
0answers
19 views

Cholesky update of $A'A+\gamma I$

Let $A$ be such that $A'A$ is positive definite and admits the Cholesky factorisation $$ A'A = LL' $$ Let us append a column-vector $c$ in $A$ and define $$\bar{A}=\begin{bmatrix}A & ...
-1
votes
0answers
8 views

Banded symmetric Toeplitz linear system

What is the best (if such exists in terms of stability, efficiency etc.) matrix decomposition (or any method) for a banded, symmetric, indefinite Toeplitz linear system? Let's say, we have a linear ...
0
votes
1answer
34 views

Inequality involving Moore-Penrose pseudoinverse

Let $A=\begin{bmatrix}A_1\\A_2\end{bmatrix}\in \mathbb{F}^{(n+m)\times n}$, with $A_1\in \mathbb{F}^{n\times n}$ and non singular, and $\mathbb{F}=\mathbb{C}$ or $\mathbb{R}$. Show that $$\lVert ...
0
votes
0answers
39 views

Sum of squares of eigenvalues

Let $\Lambda(A)$ be the sequence of eigenvalues including repeated eigenvalues, if there exist. Show that $$\inf_{X\mbox{ not singular }} \lVert X^{-1}AX\rVert_F^2=\sum_{\lambda\in \Lambda(A)} ...
0
votes
1answer
38 views

How to determine general form of line equation in 3D from 2 points without using vectors, matrices, etc

For a 2D line equation in General Form ($ax + by + c = 0$) it is possible to calculate all coefficients from two given points as follows: $a = y_1-y_2$ $b = x_2-x_1$ $c = (x_1-x_2) y_1 + (y_2-y_1) ...
0
votes
1answer
15 views

What does the quadratic form $0.5x^T Ax^T-b^Tx$ find the minimum of?

I'm trying to work through example 2, from here. We start by defining a symmetric positive definite matrix $A$: $\begin{pmatrix} 1.2054 & 0.6593 &1.2299 & 1.2577 & 1.0083\\ 0.6593 ...
0
votes
1answer
36 views

LU decomposition with pivot

I'm trying to LU decompose, with pivoting, the following matrix ($A=(a_{ij})$): A = [2 1 2; 1 0 3; 4 -3 -1]; % matlab I cannot make out from my literature ...
0
votes
1answer
20 views

Strategies for evaluating the action of the solution to a Sylvester equation on a vector

I have a Sylvester equation $AX+XB=C$ with a unique solution. I don't actually need $X$, but rather the matrix-vector product $Xv$ (for some known $v$). It seems most literature concerns itself with ...
1
vote
3answers
29 views

Matrix norm relation

I've been trying to solve this for 3 hours.. If $A$ is an $n \times n$ matrix with $\|A\|<1$ in any norm, then show that $\|(I-A)^{-1}\| \leq \frac {1}{1-\|A\|}$. My trying is: $$ ...
1
vote
1answer
29 views

Perturbation of roots in Wilkinson's polynomial

I am studying numerical analysis. When I read the online definition I found on this paragraph: Suppose that we perturb a polynomial $p(x) = Π (x−α_j)$ with roots $α_j$ by adding a small multiple ...
0
votes
0answers
28 views

QR-decomposition with Givens-rotations

I want to compute the QR-decomposition of the following matrix, with the additional requirement that the diagonal elements $R_{ii}$ be positive $$A = \begin{bmatrix} 3 & -2 & \sqrt ...
0
votes
0answers
31 views

Inverted pendelum Matrix numerical derivative

Here I've written a dynamic function as : ...
1
vote
1answer
28 views

Proof that $ ||f|| = \sqrt{\sum_{k=0}^{n}p(x_k)f(x_k)^2} $ is normed vector space

I've to prof given $X = \{x_1, x_2, ..., x_n\}$ and function $p$ with property $p(x: X) > 0$ that equation $ ||f|| = \sqrt{\sum_{k=0}^{n}p(x_k)f(x_k)^2} $ is norm on discrete set $X$. This ...
0
votes
1answer
33 views

How to generalize C from A and B.

I have Two matrix $A=\left( \begin{array}{ccc} \text a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{array} \right)$ and $B=\left( ...
1
vote
0answers
44 views

Analytic Bounds for Eigenvalues of a 2x2 Block Matrix

I am trying to find conditions under which all eigenvalues of M will have nonpositive real part (i.e. M is negative semidefinite, I think). $$M = \begin{bmatrix} A & BE^T\\ CE & D\\ ...
1
vote
0answers
12 views

Numerical algorithm for largest Eigenvalue problem

I am dealing with calculating an eigenvalue problem for differential operator of order 4: $$ \alpha \cdot\Delta^2 u+\Delta u-\Delta(u\cdot u_p(x))=\lambda u $$ where $\alpha\in \mathbb{R}$, $\Delta$ ...
3
votes
1answer
23 views

How can one show that : $|u_{n+1}-\sqrt{2}|\le\frac{1}{4}|u_n-\sqrt{2}|$

$U_n$ numerical sequence such that : ( For all natural numbers $n$ ) $U_{n+1}=1+\dfrac{1}{1+U_n}$ and $U_0=1$ How can one show that : $|U_{n+1}-\sqrt{2}|\le\frac{1}{4}|U_n-\sqrt{2}|$ I arrived to ...
1
vote
2answers
39 views

linear least squares with equality constraints

I am looking for iterative procedures for solution of the linear least squares problems with equality constraints. That is, my problem is to solve $$\min_{x} \lVert{Ax-b} \rVert _2, \ ...
0
votes
1answer
60 views

What should I know about half vectorization and Kronecker product to do this matrix differentation?

I have a scalar function as follows: \begin{equation*} \ell(\beta, \Sigma, \mu, \Lambda) = \sum_{i=1}^{m} \left[\boldsymbol{y}_{i}^{T} \left(X_{i}\beta + Z_{1} \mu_{i} \right) - ...
1
vote
0answers
27 views

Computing Cholesky Factorisation by Hand

It is a common exam problem to compute the Cholesky factorisation of a small (typically 4x4) matrix. I know that this can be done by first finding the matrix $U$ in the $LU$-decomposition (e.g. by the ...
1
vote
1answer
23 views

compare complexity of matrix transpose

Given 2 matrices: $X(rows=m,cols=n)$ and $Y(rows=m,cols=1)$, which of the following operations is computationally easy, i.e., easy on the machine? $$X^{T} \times Y \\ or \\ (Y^{T} \times X)^{T} $$
0
votes
3answers
43 views

Reconstruct a matrix from given eigenvalues

I wanted to know how can I reconstruct a matrix just from its given eigenvalues. I'm really sorry, cause after working on it for 3 days, I haven't any idea about how to do this, therefore I haven't ...
0
votes
1answer
23 views

How do I perform Gram-Schmidt on floating point vectors with epsilons in them?

Let $\epsilon$ be a small positive number such that $1+\epsilon$ and $3+2\epsilon$ are machine numbers but $3+2\epsilon + \epsilon^{2}$ is computed to be $3 + 2\epsilon $. Now, let the (classical) ...
0
votes
0answers
33 views

Way to verify a least-squares solution without actually solving for $x$ and $y$?

I just found the least squares solution of the system $\mathbf{x}A = \mathbf{b} = \begin{pmatrix} x & y \end{pmatrix}\begin{pmatrix} 3 & 2 & 1 \\ 2 & 3 & 2\end{pmatrix} = ...
10
votes
2answers
69 views

How to get the SVD of $2AA^T-diag(AA^T)$ given $A$ and its SVD $A=USV^T$?

Given a matrix $A\in R^{n\times d}$ with $n>d$, and we can have some fast ways to (approximately) calculate the SVD (Singular Value Decomposition) of $A$, saying $A=USV^T$ and $V\in R^{d\times d}$. ...
0
votes
0answers
30 views

roots of Padé approximating polynomials to the exponential function

I need to obtain (numerically) the roots of the denominator in the Padé approximation to the exponential function $e^{-x}$, in Python. I can calculate its coefficients in closed form (see below). But ...
1
vote
0answers
25 views

Perturbation of a linear homogeneous equation system

Let $A$ be a $n\times(n+1)$ matrix, full row rank. Let $\tilde A=A+\Delta A$ be a perturbation of $A$, again with full row rank. I am interested what is known about bounds on the angle between the ...
2
votes
1answer
48 views

Inverse of a matrix defined by a function

I have a matrix $M$ whose elements are defined by some function $$M_{ij} = f ( |i-j| ) $$ Is it possible to derive a function which defines the elements of the matrix inverse $M^{-1}$ i.e. ...
1
vote
0answers
15 views

Non-linear ODE with diagonal matrix

I have a differential equation of this form: $\frac{dX}{dr}(r)$= M(r)X(r)$ + (\sum_{i}X_i) D(r)X(r)$ $X(r)$ is a size n vector. $M(r)$ and $D(r)$ are n x n matrices with $D(r)$ diagonal. They are ...
0
votes
1answer
17 views

tridiagonal block matrix

Let us consider a linear system of equations $$ Ax=b $$ Where $A$ is a block tri-diagonal matrix, which is given by $$ \begin{eqnarray} A=\left[\begin{array}{ccccc} A_{11} & A_{12} & \dots ...
1
vote
0answers
27 views

Existence of Non-Commutative $4 \times 4$ Matrix Multiplication Algorithm

This paper by a Russian gentleman gives an optimal (?) algorithm for $3$ $\times$ $3$ matrix multiplication. It beats a previously known method by reducing the total number of discrete operations from ...