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

learn more… | top users | synonyms

1
vote
1answer
207 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
472 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
108 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
836 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
346 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 ...
3
votes
1answer
1k 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
88 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
76 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
386 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
939 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 ...
3
votes
1answer
584 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
1answer
127 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
266 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
628 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
91 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 ...
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
982 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
89 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
3answers
764 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
136 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
114 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
663 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
365 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 ...
3
votes
3answers
569 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
280 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
217 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 ...
4
votes
0answers
714 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
111 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
327 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
102 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
664 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
717 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
156 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$ ...
1
vote
1answer
548 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
192 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 ...
0
votes
1answer
132 views

Suitable Loss function for Order preserving Factoring of a matrix?

(Old-Question) Given a $n\times n$ symmetric matrix $X$, I would like to factor it using a vector $c$ of size $n \times 1$ such that: $\sum_{i,j} [X_{ij} \cdot c_i\cdot c_j]$ is minimum. How can I ...
3
votes
1answer
966 views

Factorize a Symmetric matrix as an 'Approximation' with an outer product.

(deprecated-taken back based on discussion(OLD)) What is a good way to factor a symmetric matrix $X$ as an outer product of two vectors $u$ and $v$. i.e, Find two vectors $u$ and $v$ such that ...
5
votes
2answers
345 views

Precision and performance of Euclidean distance

The usual formula for euclidean distance that everybody uses is $$d(x,y):=\sqrt{\sum (x_i - y_i)^2}$$ Now as far as I know, the sum-of-squares usually come with some problems wrt. numerical ...
4
votes
2answers
194 views

solution to $\min \|A-BXC \|$

I have the following problem. Let $A$, $B$ $C$ be real-valued matrices of size $m \times q$, $m \times n$, $p\times q$ respectively. I would like to find matrix $X$ of size $n\times p$ and maximum ...
1
vote
2answers
116 views

Calculate sum of ONB

Here's a homework question: Let ${u_1, \ldots, u_n}$ be an ONB in $C^n$. Assuming that $n$ is even, compute $$||u_1 - u_2 + u_3 -\cdots - u_n||$$ I have no idea how to solve this. Can anyone help? ...
1
vote
0answers
56 views

formulas for exact values of singular values in low dimension?

Are there formulas for the singular values of a real matrix in low dimension, i.e. for a $2 \times 2$ matrix or a $2 \times 3$ matrix? Any comment is welcome.
0
votes
1answer
253 views

Norm $\|A\|$ is not induced by any vector norm [duplicate]

Possible Duplicate: Subordinate matrix norm I have a question in my homework for Numerical Linear Algebra, which is as follows: Show that the norm $\|A\| = \max \limits_{i, j} |a_{i,j}|$ ...
10
votes
2answers
1k views

Augmented Reality Transformation Matrix Optimization

i am a software developer, i'm working on an Augmented Reality system. I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast. Here's the situation: ...
1
vote
0answers
150 views

The fastest algorithm of computing Principal eigenvector of a non-negative-entries matrix

I am studying the QR algorithm, is it the fastest one in this situation?
0
votes
1answer
595 views

Could explain me how eigenvector helps with compute gradient and how make differentiate operation on decrete space like digital image?

Could you explain me how eigenvector helps with compute gradient and how make differentiate operation on descrete space like digital image? I know that this question is so connected with computer ...
8
votes
1answer
1k views

Using the Arnoldi Iteration to find the k largest eigenvalues of a matrix

I'm trying to obtain a general understanding of this algorithm which determines the k-largest eigenvalues of a matrix $A\in \mathbb{R}^{n\times n}$. How I see it: power iteration: take random ...