2
votes
0answers
23 views

3-sigma Ellipse, why axis length scales with square root of eigenvalues of covariance-matrix

This is my first post on math.stackexchange and i am not a mathematician, but i took some undergrad math courses and some grad mathematical modelling courses, so i come with a basic understanding of ...
0
votes
0answers
31 views

Complexity of the power method

I'd like to find out what the complexity of the power method is depending on the size of the matrix $A \in \mathbb{R}^{n\times n}$ given that the algorithm runs until a certain stop criterion. I.e. ...
3
votes
2answers
56 views

Power iteration

If $A$ is a matrix you can calculate its largest eigenvalue $\lambda_1$. What are the exact conditions under which the power iteration converges? Power iteration Especially, I often see that we ...
1
vote
0answers
28 views

Influence of preconditioning on degenerate eigenvectors

I'm using a hierarchical decomposition of a sparse matrix $A$ as suggested here. I find that the method essentially finds eigenvectors using the QR algorithm. $A$ has some eigenvalues with ...
1
vote
1answer
52 views

Efficient method for determining to the most positive eigenvalue of a matrix

I am trying to implement an algorithm that requires knowing the largest $\textbf{positive}$ eigenvalue of a $\textbf{real symmetric, non-sparse}$ matrix and the corresponding eigenvector. The actual ...
1
vote
2answers
39 views

How to figure out the spectral radius of this matrix

$$A=\begin{array}{ccc} 0 & 1/2 & 0 & \cdots & 0 \\ 1/2 & 0 & 1/2 &\cdots& 0\\ 0 & 1/2 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots &\ddots ...
1
vote
0answers
45 views

Numerical algorithm to solve quadratic eigenvalue problem.

Given the equation $$-4 \left(a^2+a (n-1) (2 t^2-1)\right) \left(\sum _{i=0}^n \alpha_i t^{2 i}\right)^2 \\ +\frac12 \left(\sum _{i=0}^n \alpha_i t^{2 i}\right) \left(t \left(8 a (t^2-1)+1\right) \sum ...
7
votes
1answer
133 views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
1
vote
1answer
64 views

Proof that eigenvector corresponding to simple eigenvalue is continuous

Let $\lambda$ be a simple eigenvalue of $A \in L(C^n)$ and let $x$ be the corresponding eigenvector. Then for $E \in L(C^n)$, $A+E$ has an eigenvalue $\lambda(E)$ and an eigenvector $x(E)$ such that ...
2
votes
1answer
47 views

Least squares problem with orthonormality constraints

Given $y_1,\ldots,y_n\in \mathbb{R}$,$w\in \mathbb{R}^d$, and $x_1,\ldots x_n\in \mathbb{R}^D$, how do we solve the following optimization problem \begin{align} \min_A \sum_{i=1}^n (y_i-w^TA^Tx_i)^2\\ ...
0
votes
0answers
42 views

Francis Algorithm (Implicit QR Algorithm)

In Numerical Analysis, we are touching upon QR and Francis Algorithm. I understand that for Francis's Algorithm, we reduce the matrix to its upper Hessenberg form using Householder transform. What I ...
2
votes
1answer
34 views

Eigenvalue of (1-0) matrix

Assume I have 2 matrices, each of size nxn with only 1 and 0 as entries in both. (n>10) The first matrix (call it A) has each row summing up to 2 (ie: on each row, it has two "1" and n-2 "0"). It is ...
2
votes
0answers
121 views

Standard symmetric tridiagonal matrix Eigenvalue decomposition algorithm?

Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm (here). I need to code this on C++ for my personal project. This algorithm involves the eigenvalue ...
0
votes
3answers
62 views

About matrix products $A^{T}A$ and $ AA^{T} $

I'm investigating the relationship between 2-norms and eigenvalues of $A^{T}A$ and $ AA^{T} $, in order to better understand the SVD decomposition. How can I prove that $A^{T}A$ and $ AA^{T} $ are ...
2
votes
2answers
173 views

Power iteration sign of eigenvalue?

I need to write a program which computes all eigenvalues and corresponding eigenvectors. I'd like to use power iterations method (I know that it's not good but it's really necessary). my algorithm ...
0
votes
0answers
50 views

what is the meaning/characteristics of the component-wise product of right and left eigenvectors.

I have a generic, but seemingly simple question : what is the meaning/characteristics of the component-wise product of right and left eigenvectors (for the same eigenvalue of course) ? let's call ...
0
votes
1answer
60 views

Completeness of eigenvectors of Hermitian Matrix.

How do you show that eigenvectors of a Hermitian matrix form a complete set of basis?
4
votes
4answers
270 views

How to find 2x2 matrix with non zero elements and repeated eigenvalues?

I need to find a 2x2 matrix with non zero elements that has eigenvalue = 1 repeated (double). How can i do that? Thanks!
1
vote
2answers
42 views

Can you compute rank r factorization of a n*n matrix in time O(n^2 r)?

I am wondering if you can compute the SVD/eigenvectors of a rank r matrix of size n*n in time O(n^2 r)? My understanding is that standard eigenvector computations involve bringing matrix into ...
0
votes
0answers
50 views

is 'chasing the bulge' in the implicit QR algorithm exactly the same as reducing a general matrix to hessenberg form?

When performing the implicit QR algorithm, there's a part where you 'chase the bulge' down the diagonal. While it may not necessarily be numerically or computation-time equivalent, is that ...
0
votes
1answer
46 views

Generalized minimal residuals: eigenvalues and sets of functions

Can someone help me on this exercise (2 parts)? Thanks! Suppose that $S \subseteq \mathbb{C}$ is a set whose convex hull contains $0$ in it's interior (so $S$ is contained in no half-plane ...
0
votes
1answer
94 views

On eigenvalues, hermitian matrices and SVD

Are my ideas on the following "true or false"-statements correct? If $A$ is hermitian and $\lambda$ is an eigenvalue of $A$, then $|\lambda|$ is a singular value of $A$. My answer would be ...
1
vote
1answer
49 views

What is the range of this function

Let $\lambda_{1}(X)$ be the larger eigenvalue of the $2$ eigenvalues of a symmetric matrix X. For fixed real numbers $a,b,c,d$, what is the range of $\lambda_{1}\left(diag\left(a,b\right)-U\cdot ...
4
votes
1answer
662 views

Sum of eigenvalues and singular values

How one can prove that for a matrix $A\in \mathbb{C}^{n\times n}$ with eigenvalues $\lambda_i$ and singular values $\sigma_i$, $i=1,\ldots,n$, the following inequality holds: $$ \sum_{i=1}^n ...
0
votes
1answer
54 views

$\lambda_{min}\left (\frac{A+A^*}{2} \right )\leq \sigma_{min}(A)$

For $A \in \mathbb{C}^{n \times n}$, how to show that $\displaystyle \lambda_{min}\left (\frac{A+A^*}{2} \right )\leq \sigma_{min}(A)$?
2
votes
2answers
515 views

Minimum eigenvalue and singular value of a square matrix

How to show that the relationship $\left | \lambda_{min} \right | \geq \sigma_{min}$ holds between the minimum eigenvalue and singular value of a square matrix $A \in \mathbb{C}^{n \times n}$?
0
votes
1answer
261 views

Largest and smallest eigenvalues of a hermitian matrix

How to show that the largest and smallest eigenvalues of a hermitian matrix $A \in \mathbb{C}^{n \times n} $ can be found as: $\displaystyle \lambda_{max} = ...
1
vote
1answer
87 views

Eigenvalues of discretized linear integral operator

Suppose I have the following kernel operator: $Af(x) = \int_{-1}^1 K(x-y)f(y)dy$ which is also positive and compact. Hence, it has a countable set of positive eigenvalues. Suppose those eigenvalues ...
4
votes
2answers
3k views

Power iteration smallest eigenvalue?

I need to write a program which computes the largest and the smallest (in terms of absolute value) eigenvalues using both Power Iteration and Inverse Iteration. I can find them using the Inverse ...
6
votes
0answers
257 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 ...
3
votes
2answers
183 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 ...
0
votes
1answer
95 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 ...
2
votes
0answers
76 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
86 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 ...
1
vote
0answers
120 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$ ...
1
vote
0answers
162 views

Simultaneous Eigenvalue Problem

I have what I think is a simultaneous eigenvalue problem in three parameters: $$\alpha A_1x + \beta B_1x + \gamma C_1x + D_1x = 0$$ $$\alpha A_2x + \beta B_2x + \gamma C_2x + D_2x = 0$$ $$\alpha A_3x ...
1
vote
1answer
227 views

Similar matrix proof

$A$ and $B$ are similar matrices, if $B=PAP^{-1}$ holds for a square, non-singular matrix $P$. Now am wondering if $S^{-1}T$ and $S^{-1/2}TS^{-1/2}$ are similar matrices? Am looking for a proof for it ...
3
votes
1answer
117 views

Orthogonality, Maximization and Eigen-Solution

I Have read that for a matrix of reals $Y$ and a p.s.d matrix $B$ that the Maximum of $ f(Y)=Tr(Y^TBY)$ subject to $Y^TY = I$ is achieved when $span(Y)$ equals the span of the first $d$ ...
3
votes
1answer
391 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 ...
0
votes
3answers
584 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
129 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 ...
3
votes
0answers
602 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, ...
1
vote
0answers
143 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?
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 ...
-1
votes
2answers
849 views

Library for Jacobi eigenvalue algorithm [closed]

I am looking for a C or C++ or fortran library that implements the Jacobi eigenvalue algorithm: http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm do you know if it is available?
2
votes
2answers
399 views

Numerical Linear Algebra - Finding the eigenvector associated with a known eigenvalue

I have written a linear solver employing Householder reflections/transformations in ANSI C which solves Ax=b given A and b. I want to use it to find the eigenvector associated with an eigenvalue, like ...
3
votes
1answer
352 views

Eigenvectors of a matrix reduced to tridiagonal

I am implementing an algorithm to calculate eigenvalues and eigenvectors of a symmetric matrix in a GPU. In order to calculate the eigenvalues I first reduced the matrix to the tridiagonal form using ...
5
votes
2answers
489 views

When does an eigenvector of a matrix contain only a constant?

When I compute the eigenvectors of a certain matrix, the first of them is composed entirely of a single constant. What properties of a matrix lead to this result? Update By "a vector composed ...
3
votes
0answers
478 views

Numerical methods to find eigenvectors with 0 eigenvalue

I'm curious if there's any numerical way of directly finding the eigenvectors with eigenvalue 0. If I didn't have to do it directly, I would probably do it like this in pseudocode: ...