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

learn more… | top users | synonyms

0
votes
1answer
617 views

norm less than 1 matrix theory

Let $A$ be any $n \times n$ matrix and $\| \cdot \|$ be the matrix norm induced by vector norm on $\mathbb{R}^n$ (Euclidean n-dimensional space). If $\|I - A\| < 1$, then show that $A$ is ...
1
vote
2answers
120 views

Matrix norm less than $1$ iteration

Is the following true always for a matrix norm $$\lVert AB\rVert \leqslant \lVert A\rVert \cdot \lVert B\rVert \text{ ?}$$ Related to this given $r$ is positive constant, $H$ is symmetric positive ...
1
vote
0answers
127 views

fixed point spectral radius

We have the following stationary matrix iteration $$x_{k+1} = Mx_k + c$$ where $M$ is nxn matrix and $c$ is a vector. Let $r(M)$ denote the spectral radius of $M$. Show that spectral radius ...
2
votes
2answers
226 views

least square problem normal equations

Can you give an example which shows that loss of information can occur in forming the normal equations. How is accuracy improved using iterative improvement? Thank you
2
votes
1answer
135 views

Cholesky factorization counterexample

Could you give a counter example of a symetric matrix for which the Cholesky factorization does not exist? Also why does any eigenvalue solver have to be iterative?
5
votes
3answers
154 views

how can a matrix vector product reduce to a scalar?

I have an Excel spreadsheet with the following formula (paraphrased): ...
2
votes
0answers
155 views

Showing that the least-square method minimizes error

Assume that the relation between temperature and time is defined as follows: $$T = A^kC$$ We can find parameters $A$ and $C$ using the least-square method. The given relation is not linear, but we can ...
2
votes
0answers
56 views

commuting a LU factorisation

Consider the permutation matrix $P= \begin{pmatrix} 0 & \cdots & 0 & 1 \\ 0 & \cdots & 1 &0 \\ \vdots & \ddots & \vdots & \vdots \\ 1 & \cdots ...
7
votes
0answers
297 views

Computing the SVD factorization on C++ (using the proof of the existence of the SVD factorization)

I am doing a C++ program that computes the SVD factorization of a real matrix A without using any known library of algebra that contains the implementation. In addition, QR descomposition is not ...
1
vote
1answer
62 views

Help regarding a weird Matrix

Hi I have a matrix of the following form arising by discretization of a system of PDEs. I am working to get the invertibility of the Matrix. Can some one help me or at least give me some reference on ...
2
votes
0answers
164 views

Check for Ill Conditioned matrix

How can I efficiently check if a tridiagonal system with 1's in diagonal is ill-conditioned or not ? The common way is to get the ratio of largest and smallest singular values and see if its greater ...
2
votes
1answer
143 views

QR factorization

So I'm trying to factorize this matrix. $A= \left( \begin{array}{ccc} 3 & 0 \\ 0 & 3 \\ 4 & 0\\ 0&4 \end{array} \right)$ So I need to remove the 4 at $a_{1,3}$, however I'm a bit ...
0
votes
1answer
115 views

Shifter Power Method

If we know all the eigenvalues of a matrix A except the largest one. We want to apply shifted power iteration to get the largest eigenvalue. Something like $(A-\alpha I)$ . Then what should be the ...
3
votes
1answer
98 views

least square problem

Let $1<p<\infty $.We define the space: $L_{V}^{p}(-1,1)=\left \{ f:(-1,1)\rightarrow \mathbb{R}:\int_{-1}^{1}\left | f(x) \right |^{p}V(x)dx<\infty \right \}$ We define the norm: $\left \| ...
0
votes
1answer
70 views

Matrix existence..

How to prove that for any matrix $A\in \mathbb R^{m\times n}$ ($m\geq n$) such that $rank(A)=r$ there exists a nonsingular matrix $P$ and an orthogonal matrix $U$ such that, \begin{align*} A=U\Gamma ...
0
votes
1answer
527 views

Ray Plane Intersection Calculation

I am currently having issues with calculating plane intersection of a ray. I start with the following equation $P = P_0 +tR_t$ $R_t$ is the Unit Vector of the Trajectory. Now we have a plane ...
7
votes
1answer
169 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 ...
3
votes
3answers
183 views

What is LU factorization?

What is the most motivating way to introduce LU factorization of a matrix? I am looking for an example or explanation which has a real impact.
3
votes
0answers
102 views

QR decomposition help

What do Q and R stand for? Why must the diagonal entries of R be positive instead of just nonzero?
0
votes
1answer
126 views

Numerical linear algebra (pseudoinverse of a matrix)

Let $A$ be the matrix: $$\left(\begin{matrix} \alpha I_{n} \\ \beta I_{n} \end{matrix}\right)$$ where $\alpha,\beta\in\Bbb C$ are not both zero. Derive (a) the (reduced) QR factorization of $A$ ...
1
vote
1answer
176 views

Proof of GMRES convergence

I am working on a homework, where we have to proof that GMRES finds an exact solution of $Ax = b$ in at most m steps (with A being an $m \times m$-matrix). The proof is split up into several steps, ...
0
votes
2answers
435 views

How does the left singular value decomposition change when one duplicates a column in the original matrix?

Let $\mathbf{v}_1,\ldots,\mathbf{v}_n$ vectors in an $m$-dimensional space $V$. Taking these as column vectors of the matrix $M$, let $$ M = U\Sigma V^\ast $$ its singular value decomposition. Now, ...
3
votes
1answer
382 views

Generating random linear programming problems

I've just finished writing a a linear programming problem solver which uses the simplex method. Now I would like to start optimizing my solver but before I can do this, I need a way of reliably ...
1
vote
0answers
216 views

Numerical Linear Algebra problem (QR factorization with column pivoting)

For matrices that might be rank deficient it is common to incorporate pivoting in Householder QR factorization of A $\in$ $\Re^{mxn}$ (m $\geq$ n). Let $A^{(k)}$ denote the matrix at the start of the ...
1
vote
1answer
173 views

Floating point arithmetic

How can I prove that : a real number has a finite representation in the binary system if and only if it is of the form $$\pm \frac{m}{2^n}$$ where n and m are positive integers.
3
votes
2answers
202 views

Is the QR algorithm for computing eigenvalues efficient for today's standards?

I was looking at the QR factorization algorithm of a matrix to approach eigenvalues. At the Wikipedia page they state that it was developed in the 50's and took over the LR algorithm. They also state ...
1
vote
1answer
102 views

Eigen value minimization-Proof

The two minimization problems below are equivalent: $\min\{\mathrm{trace}(AX^TBX): XX^T=I_n\}=\min\{\mathrm{trace}(AQ^T\tilde{B}Q): QQ^T=I_m\}$, where $A,\tilde{B}$ and $Q$ are square matrices of ...
3
votes
1answer
103 views

Ax = 0 easier than Ax = b?

Is it easier (computationally speaking) to solve the matrix equation of the form $A\vec{x}=\vec{0}$ (with $\vec{x} \neq \vec{0}$) than for the general case $A\vec{x}=\vec{b}$ ?
2
votes
0answers
26 views

Re-calculate solution after altering some elements in a linear system

Problem I have a linear system: $$ Mx = b $$ $M$ is like a Band Matrix. And assume I have a solution $x_{init}$ at beginning. There will be some operations which are going to alter some elements in ...
4
votes
1answer
143 views

In terms of complexity, is there a quicker way of checking if a matrix is nonsingular than computing the determinant?

To repeat the question, let $A$ be a square matrix. We wish to determine if $A$ is nonsingular, that is, invertible. One way is compute its determinant and check if it is nonzero. However, if $A$ is ...
0
votes
2answers
249 views

Convergence of CG method

I have a question like how can we mathematically prove that for a general matrix Conjugate Gradient method will always converge within n steps in exact arithmetic ? where n is the size of the matrix. ...
6
votes
1answer
1k views

Trace minimization with constraints

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under 'either' one of these constraints: a) Sum of squares of Euclidean-distances between pairs ...
1
vote
1answer
419 views

Does conjugate gradient converge for negative definite matrices?

Guys I was reading about CG method to solve the sparse systems. I came across that the method is defined for positive definite symmetric matrices. I was wondering does it converges for negative ...
1
vote
1answer
272 views

pseudo-inverse of a matrix as a projection?

Is there an interpretation of $X^{\dagger}Y$ in terms of a projection or a least-squares formulation? Note that $\dagger$ denotes the pseudo-inverse and $X$ is a square matrix, and $Y$ is a ...
0
votes
1answer
63 views

Is it a positive semi-definite matrix?

Given a p.s.d matrix $K$, is $2\operatorname{Diag}(K)-K$ a p.s.d matrix? Here, $\operatorname{Diag}(K)$ is a diagonal matrix whose diagonal is the diagonal of $K$.
2
votes
0answers
78 views

Spectral/ Eigen-Value solution with a linear constraint?

Is there a spectral or eigen-value solution to finding $X$ such that $Tr(CX^TMX)$ is minimum for a symmetric matrix $C$ and a p.s.d matrix $M$. Also there is a linear constraint on the minimization ...
1
vote
2answers
1k views

Moore-Penrose pseudo inverse algorithm implementation in Matlab

I am searching for a Matlab implementation of the Moore-Penrose algorithm (convertable to C++) computing pseudo-inverse matrix. I tried several algorithms, "Fast Computation of Moore-Penrose Inverse ...
1
vote
1answer
129 views

trace function, eigen decomposition and optimization!

The equation \begin{align} \min_{X}~trace(CX^{T}MX) \end{align} where $C$ is symmetric and M is symmetric , p.s.d can be minimized by defining $M=F^{T}F$ ($M$ being a psd matrix, you will be able to ...
2
votes
1answer
83 views

Determining function inputs when outputs are recursively related to each other

I have a vector $\bf{b}$, and elements of this vector are generated by evaluating a rather complicated function $f(x)$ for $f(x_0), f(x_1),...,f(x_N)$. Here are the equations that constitute $f(x)$. ...
1
vote
2answers
88 views

Spectral/Eigen-value solution?

Is there a spectral or eigen-value solution to finding $d$ vectors $x_1...x_n$ such that $ \sum_{i,j=1}^{d} C_{i,j} \cdot x_i^\top M x_j $ is minimized, with $C_{i,j}$ being a constant real-scalar ...
2
votes
2answers
385 views

Methods to solve a system of many Ax=B equations using least-squares

I am working with a force measurement instrument which needs calibration via a calibration matrix. For each of a set of controlled measurements I have a vector $k$ of three known, independent values, ...
0
votes
2answers
38 views

Efficiently updating a vector

What is the most efficient way to make this linear algebra computation? I am interested in computing a vector $y^{(k)}$ that updates as shown below. $$y^{(k)} = A^k B A^k x$$ where the matrices $A,B ...
0
votes
3answers
87 views

Why change a given basis?

Why would we want to transform a vector in our normal basis (xyz axes) to another basis? The only situation I can recall is when we are looking at a force applied on an inclined plane. Are there any ...
1
vote
2answers
135 views

Difference between lsq(A,b) and A\b (on Scilab)

Can you explain me the difference between lsq(A,b) and A\b? Why do I get a positif solution when I use lsq(A,b,1)? Where can I get the source code of lsq function? Thank you.
0
votes
3answers
323 views

$A+\lambda B $ is invertible

I stumbled upon this question that I would like to ask you about: Let $A$ be a $n\times n$ matrix $(\mathbb R)$ and $B$ an invertible Matrix of size $n$ with real coefficients. I need to show that ...
9
votes
6answers
532 views

$\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)$ not diagonalizable

I would like to ask you about this problem, that I encountered: Show that there exists no matrix T such that $$T^{-1}\cdot \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} ...
3
votes
2answers
299 views

Are Trace of product of matrices- distributive/associative?

Is $\operatorname{Tr}(X^TAX)-\operatorname{Tr}(X^TBX)$ equal to $\operatorname{Tr}(X^TCX)$, where $C=A-B$ and $A$, $B$, $X$ have real entries and also $A$ and $B$ are p.s.d.
1
vote
0answers
134 views

Show that its a Generalized Eigenvalue problem

Show that the minimizer is obtained by a generalized eigenvalue problem. $$\alpha=\underset{1^TK\alpha=0; \ \alpha^TK^2\alpha=1}{\text {arg min}} \gamma ||f||_{K}^2+f^TLf$$ Details: $K$ ...
2
votes
3answers
719 views

Least norm solution to $Ax = b$

How to prove that if you have $x^*$ such that $x^*=\text{psuedoinverse}(A) b$, and $Ay=b$, then $$\Vert x^* \Vert_2 \leq \Vert y \Vert_2$$
3
votes
1answer
73 views

Compute Cholesky of $\Sigma^{-1}$ from Cholesky of $\Sigma$

Given a positive definite matrix $\Sigma$, how can I compute the Cholesky decomposition of $\Sigma^{-1}$ from the Cholesky decomposition of $\Sigma$? I know that $\left(L L^T \right)^{-1} = ...