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

learn more… | top users | synonyms

2
votes
1answer
98 views

Matrix inversion of an analytical function

Following problem: I have a function $f(x_1,x_2)$ and Im looking for the inverse $finv(x_1,x_2)$ of the function which is defined through: $\int f(x_1,y)\cdot finv(y,x_2) d y =\delta(x_1,x_2) $ ...
3
votes
1answer
594 views

Unstable linear inverse problem: which “dampening” Tikhonov matrix should I use?

A linear inverse problem is given by: $\ \mathbf{d}=\mathbf{A}\mathbf{m}+\mathbf{e}$ where d: observed data, A: theory operator, m: unknown model and e: error. The Least Square Error (LSE) model ...
0
votes
2answers
265 views

A question concerning Toeplitz matrices

I am studying Toeplitz matrices. I have to find out the eigenvalues of the following Toeplitz matrix: $$\begin{bmatrix} 2 & -8 & -24 \\ 3 & 2 & -8 \\ 1 & 3 & 2 ...
1
vote
1answer
199 views

Jacobi method and HPD Matrices

Let $A$ be HPD. Denote by $D$ the diagonal matrix obtained by observing the diagonal elements of A, i.e. $D = \operatorname{diag}(a_{11},a_{22},\ldots,a_{nn})$. I would like to show that if the ...
3
votes
1answer
413 views

Effects of elementary row operation on condition number

How does any elementary row operation on a matrix affect the condition number? Can an ill conditioned matrix be improved by just some elementary row operations? Can I improve the accuracy ...
1
vote
1answer
103 views

Minimizing the norm related with iteration method

I am working on a iteration method to compute the generalized inverse of a matrix $A$ of rank $r$ Iteration method is $X_{k+1} = X_{k} + \beta X_{k} (I - A X_{k}) $ where notations are as follows ...
4
votes
1answer
728 views

Product of positve definite matrix and seminegative definite matrix

Let $A$ a spd (symmetric positive definite) matrix and $B$ a symmetric seminegative definite matrix. Is tr $AB \leq 0$ and more general is $AB$ seminegative definite? I know that tr $AB \leq 0$ ...
0
votes
0answers
41 views

Issues with the value of the last element in Cholesky decomposition

I am trying to calculate the Cholesky decomposition of a precision matrix. I was expecting a Lower triangular matrix $L$ where $L_{ii}>0$ for all $i$. However, the last element in the diagonal is ...
0
votes
0answers
327 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $F(x)$ $F(x) = \sum_{i=1}^{M}||x_{i+1} - x_i - K(\frac{x_{i+1} + x_i}{2})||^2 + ||x_1-c_1||^2 + ||x_N-c_2||^2$ , where $x$ is a vector of $N$ scalars, $c$ are ...
2
votes
1answer
893 views

Is it possible to determine if this matrix is ill-conditioned?

I want to better understand ill-conditioning for matrices. Say we're given any matrix $A$, where some elements are $10^6$ in magnitude and some are $10^{-7}$ in magnitude. Does this guarantee that ...
0
votes
1answer
68 views

I need help to understand meaning of certain terms in a theorem

There are certain terms in the following theorem where I am finding difficulty to figure out. I need help. Theorem. Let $\mathbb{C}_{r}^{m\times n}$ denote the set of all complex $m\times n$ ...
2
votes
0answers
87 views

Need little hint to prove a theorem .

I have an iterative method \begin{eqnarray} X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots \end{eqnarray} with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
4
votes
1answer
73 views

Need little hint to prove a theorem from a paper

I have an iterative method \begin{eqnarray} X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots \end{eqnarray} with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
1
vote
1answer
349 views

Minimization of function expressed with vectors and matrices

I need to find vector $\bf{p}$ in the following system: $$\bf{0} \approx \bf{W} \left[ \bf{C}^2 \bf{p} - \bf{d} \right]$$ $$\bf{0} \approx \varepsilon \bf{p}$$ In the above, $\bf{0}$ is a vector, ...
2
votes
1answer
808 views

Fourier transform over a diagonal matrix

Let $F$ be a $100 \times 100$ DFT matrix, and $U$ be a diagonal matrix with its diagonal entries being all positive, denoted by $U=\mathrm{diag}(u_1, u_2,\cdots, u_{100})$. My question is: Under ...
0
votes
0answers
249 views

Householder Transformation

Let $\mathbf{a}\in\mathbb{R}^{n}$ be a non-zero vector. Develop a numerically stable procedure to compute a Householder transformation P such that $$P\mathbf{a}=\left(\begin{array}{c} ...
3
votes
1answer
461 views

Calculating the inertia of a real symmetric (or tridiagonal) matrix

I'm trying to find a quick method for evaluating the inertia of a real symmetric matrix, though I don't need to evaluate eigenvalues directly. The inertia of a matrix is a triple of the number of ...
2
votes
0answers
2k views

What is the algorithm for LU factorization in MATLAB?

What is the algorithm for LU factorization in MATLAB, i.e. [L,U] = lu(a)? After searching for many examples and trying to compare the result with MATLAB, they are ...
0
votes
0answers
64 views

Can this be expressed as an LLSQ problem? $||Ax - b|| = c$

I'm trying to minimize the following: $||Ax - b|| - c$ where: $A$ : $K \times M$ matrix $x$ : $M \times N$ unknowns ($M$ $N$-dimensional vectors) $b$ : $K$ $N$-dimensional vectors $c$ : $K$ ...
0
votes
1answer
124 views

more matrix inversion

Related to a previous question: Suppose I want to invert a (sparse) matrix written in block form as \begin{array}{cccc} A_{11} & A_{12} & \ldots & A_{1n}\\ A_{21} & A_{22} & & ...
0
votes
1answer
239 views

Matrix Norm - three Norm

Question: The Three-norm on $R^n$ is defined as: $$||x||_3=(|x_1|^3+\cdots+|x_n|^3)^{1/3}$$ The natural matrix norm it induces on $R^{n \times n}$ is $$||A||_3 = \max\{||Ax||_3 : ...
3
votes
0answers
510 views

Why is Cholesky factorization numerically stable

It's often stated (eg: in Numerical Recipes in C) that Cholesky factorization is numerically stable even without column pivoting, unlike LU decomposition, which usually need pivoting schemes. But ...
2
votes
2answers
87 views

Have spd $(A^TA)$ and $(B^TB)$, need $A^TB$.

Given two symmetric positive definite matrices $(A^TA)$ and $(B^TB)$ I need to compute $A^TB$. $A$ and $B$ are not given directly. $(A^TA)$ and $(B^TB)$ have the same dimensions. $A$ and $B$ are ...
0
votes
0answers
115 views

Efficient principal pivots

Background I'm working on a numerical linear algebra package in C#. I'm trying to implement a variety of "principal pivoting" methods to solve optimization problems (specifically linear ...
5
votes
6answers
1k views

A book for self-study of matrix decompositions

I am a third year math student and I noticed that there are many uses for decomposing a matrix (I mean decompositions like SVD, LU etc'). Is there a good book for self-study of the subject ? Note ...
1
vote
2answers
887 views

Show that the minimum eigenvalue of a Hermitian matrix $A$ is less than equal to the smallest diagonal element of $A$

I have a following question: Let $A \in C^{n\times n}$ be Hermitian and $\lambda_\min$ be the smallest eigenvalue of $A$, i.e., $\lambda_\min = \min\{\lambda_1, \ldots, \lambda_n\}$. Show that ...
1
vote
0answers
88 views

How to solve Rayleigh Quotient type problem?

How to solve Rayleigh Quotient type problem? $$\max (w+w_0)^tC(w+w_0) \text{ s.t. } w'w=1,$$ where $w_0$ is given. Thank you!
0
votes
0answers
57 views

Diagonalising a huge matrix of symbolic objects

I have to diagonalise this HUGE $9\times 9$ matrix with symbolic entries which are made up of three independent variables. Can you please give me a reference as to how to do such a thing ...
0
votes
3answers
672 views

Two linearly independent eigenvectors with eigenvalue zero

What is the only $2\times 2$ matrix that only has eigenvalue zero but does have two linearly independent eigenvectors? I know there is only one such matrix, but I'm not sure how to find it.
4
votes
1answer
134 views

Show the space spanned is an invariant subspace

Let $A$ be real and let $\lambda = \alpha + i \beta$ be a complex eigenvalue of $A$ with eigenvector $x + iy$, show that the space spanned by $x$ and $y$ is an invariant subspace of $A$. What I ...
1
vote
1answer
23 views

Optimization of closed (ring) transforms

I have a closed set of 4 linear matrix (3x3) transforms. Let's name them (A,B,C,D). Closed set means that $D*C*B*A=E$, where $E=eye(3)$. Their numeric representation is known from experiment and, ...
4
votes
1answer
113 views

$A, B$ sparse imply $AB$ is sparse?

Today I read the claim that if $A$ and $B$ are sparse matrices, then $AB$ is also sparse. I didn't believe it at first, but could not exhibit a counterexample. So is this claim in fact true? If so, ...
0
votes
1answer
597 views

calculating matrix rank with gaussian elimination

[The answer to my problem has been found: it was a simple sign error. the pseudo code below is fine] I have implemented an algorithm in c++ that should calculate the matrix rank of a given n x m ...
3
votes
2answers
331 views

Generating unitary matrices numerically - “close” to the identity element

EDIT: broke this into two parts - for these were two different questions. For numerically obtaining the stabilities of a matricial equation, i need to generate an ensemble of matrices that are ...
2
votes
3answers
480 views

iteration convergence

When soloving the linear equation $x=Ax+b$ (where $x$ is an unknown vector, $A$ is a matrix, and $b$ is a constant vector), one often use the follow iteration: $x_{k+1}=Ax_k +b$. Does the above ...
2
votes
1answer
265 views

Confusion with “trivial Givens rotations” being used to eliminate values in a vector

I am currently studying the QR algorithm described in Computing the eigenvalues of a companion matrix and have come to something that has me scratching my head. I'm trying to work this method out on ...
1
vote
1answer
183 views

Proving the SVD Theorem by induction on the rank of $A$

This is an exercise and it is divided into steps. The first step says: Suppose $A\in\mathbb{R}^{m\times n}$ has rank 1. Let $u_1\in\mathbb{R}^n$ be a vector in $R(A)$ such that $\left \| u_1 \right ...
0
votes
0answers
94 views

Does a single Gauss-Seidel iteration lead to unique coordinates?

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
3
votes
0answers
666 views

General properties of eigenvalues of a Jacobian matrix when premultiplied by a symmetric, positive definite matrix?

For a particular engineering problem that I'm working on, I have computed a Jacobian matrix $J$ and there is another matrix $M$ associated with the problem. $M$ is known to be symmetric, real-valued, ...
0
votes
1answer
100 views

Generating Gauss-Seidel hard system

I am writing various Gauss-Seidel algorithm parallel implementations using different programming techniques for my assignment. I have created a MATLAB script for generating strictly diagonally ...
1
vote
2answers
295 views

Given orthogonal basis what is the orthogonal complement?

The question states: Let $q_1,q_2,\dots,q_n$ be an orthogonal basis of $\Bbb R^n$ and let $S = \operatorname{span}\{q_1,q_2,\dots,q_k\}$, where $1 \le k \le n-1$. Show that $S^\perp = ...
3
votes
1answer
99 views

Check my solution to system of equations?

I have the following system of equations that I wanted to solve: $$ 2x_1+12x_2+16x_3=24\\ 7x_1+6x_2+4x_3=18\\ 3x_1+2x_2+8x_3=32\\ 9x_1+5x_2+10x_3=14 $$ I tried arranging into matrix form: $$ ...
4
votes
3answers
597 views

Books for Numerical linear algebra

I'am looking for some books for studying Numerical linear algebra methods. It could be on english or russian ​​languages, and Maple or Matlab examples preferable, but it also can be C/C++/Formal code. ...
1
vote
1answer
637 views

Simultaneous Iteration, Convergence to Eigenvectors

I have a question about the simultaneous iteration. I am currently working for an exam and I do not understand this step (taken from Numerical Linear Algebra from Trefethen/Bau): For the power ...
1
vote
2answers
149 views

$A = LDL^T \Rightarrow $all of the main diagonal entries of $D$ are positive?

$A$ is symmetric positive definite and $A = LDL^T$, where $L$ is unit lower triangular and $D$ is diagonal. I want to prove that the main-diagonal entries of $D$ are all positive. I have tried ...
3
votes
6answers
2k views

Matrix-Square Root

I was wondering about matrix square roots. What is the procedure to evaluate $(X^{T}X)^{-1/2}$? Is it by a spectral decomposition of $(X^{T}X)^{-1}$ as $U\lambda U^{T}$ followed by the square root $S$ ...
0
votes
0answers
45 views

Lower Rank Matrix

Given I have a matrix A of rank 3. I want to create a matrix of Rank 2 which is closest to A in the $ {l}_{2} $ / Frobenius norm. Let's call this matrix F. Is easy to achieve by the SVD, namely, if $ ...
0
votes
0answers
144 views

Singular value decomposition, possible property

Suppose a singular value decomposition on matrix $P\in\mathbb{R}^{n\times m}$ is given, $P=U\Sigma V^T$ with $U=[u_1,\dots, u_n]\in\mathbb{R}^{n\times n}$, $u\in\mathbb{R}^{n}$, containing the ...
1
vote
1answer
482 views

Multiplying double-centered matrix to a unit vector

Suppose an arbitrary double-centered matrix $D\in \mathbb{R}^{n\times n}$ and an unit vector $u\in \mathbb{R}^{n}$ are given. What happens to the vector after applying $Du$? Does the vector change ...
3
votes
2answers
176 views

How can I prove $\mathrm{maxmag}(A)=\frac{1}{\mathrm{minmag}(A^{-1})}$, and $\mathrm{maxmag}(A^{-1})=\frac{1}{\mathrm{minmag}(A)}$?

Using $\mathrm{maxmag}(A)=\max_{x\neq 0}\frac{\|Ax\|}{\|x\|}$, and $\mathrm{minmag}(A)=\min_{x\neq 0}\frac{\|Ax\|}{\|x\|}$ I found this quite simple to prove using a proposition stating that ...