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

learn more… | top users | synonyms

3
votes
1answer
41 views

prove that $|\lambda(H) - \lambda(B)| \leq \sqrt{||(C^HC)||_2}$

Let A, B be Hermitian square matrices and $$H = \left[\begin{array}{rr}A & C \\ C^H & B\end{array}\right]$$ Show every eigenvalue $\lambda(B)$ of B, there is an eigenvalue $\lambda(H)$ of H ...
0
votes
1answer
20 views

a matrix inverse problem

Given a matrix $X$, let $D$ be a diagonal matrix whose diagonal elements are row sums of $X$, let $I$ be an identity matrix. Now I have a resultant matrix of $Y=(I-X)^{-1}$, and I would like to ...
1
vote
1answer
21 views

Proof that strictly tri-diagonally dominant matrix has an inverse

We are given the following theorem of which we need only know the result. Theorem Suppose an $n\times n$ matrix $A= (a_{ij})$ is tri-diagonal with $a_{i,i-1}a_{i,i+1} \neq 0$, for each ...
1
vote
1answer
25 views

How does one prove the solution of minimum Euclidean Norm to the least squares problem?

If we have some $m \times n$ matrix $A$ with an $m$-vector $b$, how does one prove that the solution $x$ of the minimum Euclidean norm to the least squares problem $Ax \approx b$ is given by $$ x = ...
1
vote
1answer
47 views

convolution and associativity

Ok Let talk about this,... I am now so confused. 1-$$\mathcal{F}\Big\{c(x-x_0)b(x-x_0)\Big\}=\mathcal{F}\Big\{c(x-x_0)\Big\}\circ\mathcal{F}\Big\{b(x-x_0)\Big\}\\=\Bigg[e^{-2ix_0y}C(y) ...
0
votes
0answers
24 views

the rank of QR decomposition

I saw this in a paper, where one has a QR decomposition $C=QR$ ($C\in R^{m\times r}$, $Q\in R^{m\times r}$ is column orthogonal, $R\in R^{r\times r}$, $m>r$). However, under the condition that the ...
1
vote
1answer
39 views

Relative error of floating point in inner product

Prove that the floating point arithmetic with machine epsilon $\epsilon$ produces an inner product satisfying: $$\text{fl}(x^Ty) = x^T(y+e)$$ where $$|e_i| \leq 2n\epsilon|y_i|$$ as long as $n\epsilon ...
1
vote
1answer
37 views

Question on the spectral radius, regular splitting, and non-singularity/non-negativity

Given $A$ in $R^{nxn}$ and its regular splitting M and N (A = M - N), $M$ is nonsingular and $M^{-1}$ and $N$ are nonnegative. If the spectral radius $p(M^{-1}N)<1$, show $A$ nonsingular and ...
0
votes
3answers
43 views

How does one find the reduced Singular Value Decomposition of a row or column vector? [duplicate]

If we treat a column vector $a$ as an $n \times 1$ matrix, or a row vector $a^T$ as a $1 \times n$ matrix, how would one write out the reduced singular value decomposition of $a$?
0
votes
4answers
56 views

Is it possible to generate $A$ from a linear system of the form $Ax=b$ given $x$ and $b$?

Take a linear system of the form $Ax=b$. Usually, for obvious reasons, we want to find $x$ given $A$ and $b$. As you all know, the solutions may not be unique, or exist, and many algorithms have been ...
0
votes
0answers
64 views

Practical examples/implementation details for Gauss-Seidel method

I'm having a presentation on Gauss-Seidel iterative method, and although it isn't mandatory , I would like to have some practical examples for this method (a system of linear equations with n>=1000, ...
1
vote
1answer
56 views

How to find Housholder reflection

For example, let say I have a matrix$$ \left(\begin{array}{rrr} 3 & 3 & 0 \\ 0 & 0 & 0 \\ 4 & 1 & 3 \end{array}\right) $$ and the Householder has the form $H = I -2uu^T$, and ...
0
votes
0answers
20 views

Iterated Schur complement for block matrices

Suppose you have got a symmetric block matrix $A = \begin{pmatrix} A_{1,1} & \dots & A_{1,n} \\ \vdots & & \vdots \\ A_{n,1} & \dots & A_{n,n} \end{pmatrix}$ Suppose that ...
1
vote
1answer
55 views

Singular Value Decomposition using Jacobi Method

First time user of the site, so I apologize if my question isn't worded properly. I'm trying to implement the SVD of a square matrix using Algorithm 6 found on this website: ...
1
vote
1answer
35 views

$LDL^T$ decompositon of a symmetric matrix and a matrix determinant expression for the lower triangular entries

Let $n$ be a positive integer, and let $M$ be an integral, symmetric, nonsingular matrix. As $M$ is nonsingular, there exists an $LDL^T$ decomposition such that $D = (d_j)$ is diagonal and ...
4
votes
1answer
70 views

Prove $\min_{i}|\lambda_i| \leq |r_{jj}| \leq \max_{i}|\lambda_i|$

Let A be a normal $n \times n$ matrix with the eigenvalues $\lambda_1,...,\lambda_n$ |A| = |QR|, $|Q^HQ| = I$, $|R| = [r_{ik}]$ upper triangular matrix. Prove: $$\min_{i}|\lambda_i| \leq |r_{jj}| \leq ...
0
votes
0answers
41 views

How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...
0
votes
2answers
82 views

Prove that $q_{ki} = \lambda_1[1+ \mathcal{O}((\frac{\lambda_1}{\lambda_2})^k)] \; \text{for all } i \; \text{with} \; (x_1)_i \neq 0$

Let A be a real symmetric $n x n$ matrix having the eigenvalues $\lambda_i$ with $$|\lambda_1|>|\lambda_2| \geq ... \geq |\lambda_n|$$ and the corresponding eigenvectors $x_1...x_n$ with $x_1^Tx_k ...
0
votes
1answer
24 views

Reformulate this system of equations

I have the following systems of equations: $$ A\cdot g = \mathbb 0\\ G\cdot \mathbb 1 = w$$ $A$ is a $J\cdot I \times J\cdot I$ matrix. $g$ is a $J\cdot I \times 1$ column vector $\mathbb 0$ and ...
3
votes
1answer
65 views

Relationship between the solution to $Ax=b$ and $(A+I)x=b$

I have have a symmetric, tridiagonal, Toeplitz matrix $A$, where $A_{11} = -\frac{1}{2}$ and $A_{21} = 1$, and I need to solve the system $$ (A+I)x=b, $$ numerically where $b$ does not necessarily ...
1
vote
1answer
26 views

Trying to show convergence of a Forward Euler method based on step size restriction

I have shown that for the given ODE system, that when we apply the forward Euler method to something like \begin{align} \mathbf{y'} &= A\mathbf{y} \\ \mathbf{y}(t_{0}) &= y_{0} \\ t &\in ...
3
votes
1answer
99 views

Value of an integral involving the fractional part function

I have difficulties in evaluating the double integral defined in the following. Let $$\left\{ t \right\} = t - \lfloor t \rfloor, $$ $ t> 0$ be the fractional part function, where the ...
0
votes
0answers
11 views

Powers of matrices via the generalised Lanczos process

At each iterative step of the generalised Lanczos process for the pair of matrices (A,B), we obtain the following factorisation: $$ A Q_k = B Q_{k+1} \widehat{T}_k, $$ where $Q_k^T B Q_k = I_k$ and ...
2
votes
1answer
34 views

Technique to calculate rank of this matrix.

1) How can we calculate the rank of this matrix for $n > 3$ ? \begin{matrix} 1^2 & 2^2 & 3^2 & \cdots & n^2 \\ 2^2& 3^2 & 4^2 &\cdots & (n+1)^2 \\ ...
0
votes
0answers
43 views

Which of the following fixed point iterations will converge?

Which of the following fixed point iterations will converge? Why? Give the rate of convergence. (a) $x_{n+1} = \cos x_n$ (b) $x_{n+1} = \sin x_n$ (c) $x_{n+1} = \tan x_n$ For $10$ bonus ...
1
vote
1answer
34 views

Cholesky decomposition with unit diagonal

Let $A$ be real-valued (strictly) positive definite (P.D.) so that it has a unique Cholesky decomposition of the form $A = LL^T$ where $L$ is lower triangular. What PD matrices $A$ have a Cholesky ...
2
votes
1answer
47 views

Applied/Numerical Linear Algebra-Suggestions for Project

I am looking for suggestions for a research project in applied/numerical linear algebra. As far as requirements, there really aren't any except that the topic has to tie in somehow with numerical ...
6
votes
1answer
44 views

Floating point arithmetic operations when row reducing matrices

A numerical note in my linear algebra text states the following: "In general, the forward phase of row reduction takes much longer than the backward phase. An algorithm for solving a system is usually ...
1
vote
2answers
56 views

Explaining roundoff error when row reducing matrices

In my linear algebra textbook (in the context of row reducing and obtaining a matrix in echelon or reduced echelon form), there is a numerical note that reads as follows: "A computer program usually ...
1
vote
0answers
42 views

Least-squares solution to a transformation between coordinate frames

Suppose I have four coordinate frames in 3D space: A, B, X and ...
0
votes
0answers
20 views

Mixed Lognormal Model Calibration

Any ideas as to how to calibrate a mixed lognormal volatility model (Brigo and Mercurio 2002) for arbitrary N < 10? The paper seems vague with respect to implementation.
0
votes
0answers
14 views

LU Decopmostions with block

So both $A_{11}$ and $\hat{A_{22}}$ have $LU$ decompositions say $A_{11}=L_{1}U_{1}$ and $\hat{A_{22}}=L_{2}U_{2}$. Show that $ \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} ...
1
vote
1answer
77 views

How to obtain a convergent solution iteratively for a linear system of equations?

I am working on a problem that requires an iterative procedure to solve a linear system of equations, the system of equations in matrix form is: $$\underbrace{\begin{bmatrix} r_{11} & r_{12} ...
2
votes
1answer
26 views

How to prove Kahan's example on componentwise pertubation theory?

In Matrix Computations (4th edition) by Gene H. Golub and Charles F. Van Loan, Problem 3.5.3 asks the following problem (and citing Kahan, William. "Numerical linear algebra." Canadian Math. Bulletin ...
2
votes
0answers
18 views

Dense Rank Deficient Linear System

What are some of the best methods for solving a Dense Rank Deficient Linear System $Ax = b$, where $A$ is Dense, Symmetric but possibly Rank Deficient. I know SVD can solve it pretty nicely while ...
1
vote
1answer
27 views

Perspective transformation matrix application

I need to transform an angled photographed pice of paper to a "flat" image. I found this question & solution here on Mathematics and tried it out for the image given in the solution: The values ...
0
votes
0answers
54 views

Generalized SVD and weighted SVD

I've the following question: How should I select the $A$,$B$ matrices in the generalized singular value decomposition (GSVD) such that it solves the weighted version of the generalized singular value ...
5
votes
1answer
130 views

Convergence of Conjugate Gradient Method for Positive Semi-Definite Matrix

Let $A\in\mathbb{R}^{N\times N}$ be a positive semi-definite matrix, given $b\in\mbox{Col}\left(A\right)$ we want to solve the equation system $Ax=b$ . To add some notation, we define ...
1
vote
1answer
38 views

Any good books to practice on Endomorphisms as related to Diagonalization, Cayley-Hamilton, etc.?

Well, I am looking for books (graduate level) that covers linear maps (endomorphisms, to be specific) with emphasis on topics related to numerical linear algebra, like: diagonilzation, ...
-1
votes
1answer
38 views

Is matrix multiplication commutative for square matrices representing linear transforms?

On several occasions, I have heard that matrix multiplication is commutative for square matrices $A$ and $B$ when they represent linear transformations. Is this true? I know that in general $AB$ is ...
2
votes
0answers
45 views

Numerically stable method for angle between 3D vectors

I'm looking for a numerically stable method for computing the angle between two 3D vectors. Which of the following methods ought to be preferred? Method 1: $$ u\times v = ||u|| ||v|| \sin(\theta) ...
1
vote
1answer
76 views

Best approach for numerically computing the pseudo-inverse of a covariance matrix

What are the reasons to prefer eigenvalue decomposition over singular value decomposition for numerically computing the pseudo-inverse of a symmetric real matrix? In the case when you want to form the ...
0
votes
0answers
43 views

Finding the closest low rank correlation matrix?

I am looking to find the rank 3 correlation matrix approximation of a rank $n-1$ correlation matrix. This best approximation can be more clearly defined as the closest correlation matrix with rank 3 ...
3
votes
3answers
73 views

How to find all orthogonal matrices which commute with a given symmetric matrix?

Suppose we have a symmetric matrix $H$. I'd like to find all the orthogonal matrices $S_i$, which commute with it. Particularly I'm interested in the set of $S_i$, which are linearly independent from ...
-1
votes
1answer
20 views

QR Decomposition Inverse?

For QR Decomposition (of an n by n matrix) since A = QR, where A is a matrix, Q is an orthogonal matrix and R is the upper triangular matrix, does this mean that A$R^{-1}$ = Q? And if the above ...
0
votes
1answer
28 views

Find orthogonal operator to satisfy the transformation

everyone, here I have a question as shown in the figure. firstly ,I assume the standard matrix for the operator to be $A=[a_1, a_2, a_3]$ ,and I know the property that transpose of A=inverse of A ...
0
votes
0answers
24 views

Linear System with non zeros count constraint

I trying to solve a simple linear system: $Ax=b$ But with constraints like: $\sum{x_i}=S$, Usually S = 1. $L \le x \le U$, Lower & Upper bounds (usually $0 \le x \le 1$) And "Maximum count of ...
0
votes
1answer
25 views

Simplify the following in index notation

Simplify the following in index notation $I_{s,t}\delta_{s,n}\delta_{n,t}$ Since both $\delta$ 's contain an $n$ index does it simplify to $I_{s,t}\delta_{s,t}$ Then can you simplify further since ...
3
votes
2answers
50 views

Convergence for Conjuguate gradient method

I am trying to probe this corollary in a numerical PDE book: If $A\in \mathbb{R^{n\times n}}$ is symmetric and positive definite, then the conjugate gradient method reaches the exact solution in at ...
0
votes
1answer
40 views

An Optimal Value of a Diagonal Matrix $\Xi$ in $ H = U \Xi$

We have access to very accurate estimates of matrices $H$ and $U$ (both are $n \times k$, $n > k$) such that the following relationship holds $$ H = U \Xi$$ where $\Xi$ is a $k \times k$ diagonal ...