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

learn more… | top users | synonyms

1
vote
1answer
28 views

Comparing matrix norm with the norm of the inverse matrix

I need help understanding and solving this problem. Prove or give a counterexample: If $A$ is a nonsingular matrix, then $\|A^{-1}\| = \|A\|^{-1}$ Is this just asking me to get the magnitude of ...
1
vote
1answer
11 views

Conditioning in regards to matrix vector product

This program involves the matrix-vector computational primitive $y \leftarrow Ax$ where $x,y\in\mathbb{R}^n$ and $A\in \mathbb{R}^{n\times n}$. A is taken to be dense and banded in the two parts of ...
1
vote
1answer
27 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 ...
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
31 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$. ...
0
votes
1answer
16 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 ...
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 ...
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 ...
1
vote
1answer
48 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
1answer
29 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 ...
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 ...
2
votes
1answer
46 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 ...
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
2answers
32 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, ...
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
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) ...
1
vote
1answer
26 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
0answers
16 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 ...
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
0answers
251 views

update cholesky factorization

I need to compute the Cholesky factorization of $H'H$ where $H$ is a big sparse rectangular matrix. After that $H$ is modified by adding several lines. That is H_n = [H ; line_1 ; ... ; line_n] in ...
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 & ...
2
votes
2answers
1k views

Gauss-Seidel method convergence algorithm

From Wikipedia: The convergence properties of the Gauss–Seidel method are dependent on the matrix A. Namely, the procedure is known to converge if either: ...
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 ...
-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
0answers
40 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
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
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 ...
-1
votes
2answers
546 views

A projection $P$ is orthogonal if and only if its spectral norm is 1 [closed]

I have to show what the title says. A projection $P$ is orthogonal if and only if its spectral norm is $1$. I suppose I have to use the following identity: ...
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
29 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 ...
2
votes
2answers
447 views

Space spanned by matrices

I have a set of $5$ by $5 $matrices, $M_1,M_2,...,M_{19} ,M_{20}$. I want to try to find a basis from this set and also to find relationships between these matrices. This is how I think I should ...
5
votes
3answers
5k views

Power iteration smallest eigenvalue?

I need to write a program which computes the largest and the smallest (in terms of absolute value) eigenvalues using both Power Iteration and Inverse Iteration. I can find them using the Inverse ...
1
vote
1answer
775 views

How to find the Householder transformation?

Assume $x=(1,0,4,6,3,4)^T$. Find a Householder transformation and a positive number $\alpha$ such that $Hx=(1,\alpha,4,6,0,0)^T$. I'm sorry that I don't know how to start with this problem. A ...
0
votes
0answers
31 views
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 ...
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
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} $$
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 ...
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
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) ...