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

learn more… | top users | synonyms

1
vote
1answer
45 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
18 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
38 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
37 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$. ...
2
votes
1answer
28 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
17 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
17 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
56 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
60 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
32 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
61 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
35 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
43 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
42 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
39 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
29 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
61 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
23 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
21 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
26 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 & ...
0
votes
1answer
36 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
54 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
60 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
2answers
21 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
47 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
21 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
31 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
56 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
31 views

Inverted pendelum Matrix numerical derivative

Here I've written a dynamic function as : ...
1
vote
1answer
30 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
35 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
46 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
24 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 ...
2
votes
2answers
49 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
82 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) - ...
2
votes
0answers
33 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
26 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
48 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
29 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
39 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} = ...
12
votes
2answers
82 views

How to get the SVD of $2AA^T-\operatorname{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
42 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
28 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
51 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
16 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
20 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
30 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 ...
0
votes
1answer
21 views

Splitting Method

Consider the iteration matrix for the general splitting method $M=I-N^{-1}A$ where $N$ is any invertible matrix. Show that if $\lambda =1$ is an eigenvalue of $M$. then $A$ cannot be invertible. I ...
1
vote
1answer
25 views

Change multiple positions of points on circles with different radius

There are some points which are placed on a circular path: Now I want to change the position of some points equals to the distance value(d) respected to their path. I'm using this formula to ...