Which eigenvectors do MATLAB/numpy display when eigenvalues are repeated [closed]

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

When a matrix has repeated eigenvalues, which eigenvectors do linear algebra libraries (particularly MATLAB/numpy) display?

For example, in MATLAB, I tried [eigvals,eigvecs] = eig([2 0 0; 0 2 0; 0 1 1]) and got

eigvecs =

 1.0000 0 0
 0 0 0.7071
 0 1.0000 0.7071

eigvals =

 2 0 0
 0 1 0
 0 0 2

The eigenvectors corresponding to eigenvalue $2$ are anything spanned by the first and third columns of eigvecs, but I was wondering how these two columns were chosen.

Not sure if this is an appropriate question for this forum, but I observe identical eigenvectors from both MATLAB and numpy, which is why I hypothesized that maybe there's a mathematical reason for which eigenvectors are chosen, that's common for multiple linear algebra libraries, and therefore the question belongs on math.stackexchange.

linear-algebra eigenvalues-eigenvectors matlab python

share|cite|improve this question

asked Jul 20 at 6:42

Rakesh Sinha

186

closed as off-topic by Piyush Divyanakar, Delta-u, José Carlos Santos, Taroccoesbrocco, max_zorn Jul 21 at 1:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is not about mathematics, within the scope defined in the help center." – Delta-u, José Carlos Santos, Taroccoesbrocco

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I'm voting to close this question as off-topic because this is question about a design choice in programming and should be moved to stackoverflow.
  – Piyush Divyanakar
  Jul 20 at 8:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @PiyushDivyanakar This is not a programming question. This is a numerical linear algebra question. Why is every time someone asks a numerical analysis question people attempt to close it?
  – RHowe
  Jul 20 at 15:02
  

  
  
  
  

add a comment | 

up vote
1
down vote

favorite

When a matrix has repeated eigenvalues, which eigenvectors do linear algebra libraries (particularly MATLAB/numpy) display?

For example, in MATLAB, I tried [eigvals,eigvecs] = eig([2 0 0; 0 2 0; 0 1 1]) and got

eigvecs =

 1.0000 0 0
 0 0 0.7071
 0 1.0000 0.7071

eigvals =

 2 0 0
 0 1 0
 0 0 2

The eigenvectors corresponding to eigenvalue $2$ are anything spanned by the first and third columns of eigvecs, but I was wondering how these two columns were chosen.

Not sure if this is an appropriate question for this forum, but I observe identical eigenvectors from both MATLAB and numpy, which is why I hypothesized that maybe there's a mathematical reason for which eigenvectors are chosen, that's common for multiple linear algebra libraries, and therefore the question belongs on math.stackexchange.

linear-algebra eigenvalues-eigenvectors matlab python

share|cite|improve this question

asked Jul 20 at 6:42

Rakesh Sinha

186

closed as off-topic by Piyush Divyanakar, Delta-u, José Carlos Santos, Taroccoesbrocco, max_zorn Jul 21 at 1:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is not about mathematics, within the scope defined in the help center." – Delta-u, José Carlos Santos, Taroccoesbrocco

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I'm voting to close this question as off-topic because this is question about a design choice in programming and should be moved to stackoverflow.
  – Piyush Divyanakar
  Jul 20 at 8:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @PiyushDivyanakar This is not a programming question. This is a numerical linear algebra question. Why is every time someone asks a numerical analysis question people attempt to close it?
  – RHowe
  Jul 20 at 15:02
  

  
  
  
  

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

When a matrix has repeated eigenvalues, which eigenvectors do linear algebra libraries (particularly MATLAB/numpy) display?

For example, in MATLAB, I tried [eigvals,eigvecs] = eig([2 0 0; 0 2 0; 0 1 1]) and got

eigvecs =

 1.0000 0 0
 0 0 0.7071
 0 1.0000 0.7071

eigvals =

 2 0 0
 0 1 0
 0 0 2

The eigenvectors corresponding to eigenvalue $2$ are anything spanned by the first and third columns of eigvecs, but I was wondering how these two columns were chosen.

Not sure if this is an appropriate question for this forum, but I observe identical eigenvectors from both MATLAB and numpy, which is why I hypothesized that maybe there's a mathematical reason for which eigenvectors are chosen, that's common for multiple linear algebra libraries, and therefore the question belongs on math.stackexchange.

linear-algebra eigenvalues-eigenvectors matlab python

share|cite|improve this question

asked Jul 20 at 6:42

Rakesh Sinha

186

When a matrix has repeated eigenvalues, which eigenvectors do linear algebra libraries (particularly MATLAB/numpy) display?

For example, in MATLAB, I tried [eigvals,eigvecs] = eig([2 0 0; 0 2 0; 0 1 1]) and got

eigvecs =

 1.0000 0 0
 0 0 0.7071
 0 1.0000 0.7071

eigvals =

 2 0 0
 0 1 0
 0 0 2

The eigenvectors corresponding to eigenvalue $2$ are anything spanned by the first and third columns of eigvecs, but I was wondering how these two columns were chosen.

Not sure if this is an appropriate question for this forum, but I observe identical eigenvectors from both MATLAB and numpy, which is why I hypothesized that maybe there's a mathematical reason for which eigenvectors are chosen, that's common for multiple linear algebra libraries, and therefore the question belongs on math.stackexchange.

linear-algebra eigenvalues-eigenvectors matlab python

share|cite|improve this question

asked Jul 20 at 6:42

Rakesh Sinha

186

share|cite|improve this question

share|cite|improve this question

asked Jul 20 at 6:42

Rakesh Sinha

186

asked Jul 20 at 6:42

Rakesh Sinha

186

asked Jul 20 at 6:42

Rakesh Sinha

186

186

closed as off-topic by Piyush Divyanakar, Delta-u, José Carlos Santos, Taroccoesbrocco, max_zorn Jul 21 at 1:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is not about mathematics, within the scope defined in the help center." – Delta-u, José Carlos Santos, Taroccoesbrocco

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by Piyush Divyanakar, Delta-u, José Carlos Santos, Taroccoesbrocco, max_zorn Jul 21 at 1:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is not about mathematics, within the scope defined in the help center." – Delta-u, José Carlos Santos, Taroccoesbrocco

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I'm voting to close this question as off-topic because this is question about a design choice in programming and should be moved to stackoverflow.
  – Piyush Divyanakar
  Jul 20 at 8:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @PiyushDivyanakar This is not a programming question. This is a numerical linear algebra question. Why is every time someone asks a numerical analysis question people attempt to close it?
  – RHowe
  Jul 20 at 15:02
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I'm voting to close this question as off-topic because this is question about a design choice in programming and should be moved to stackoverflow.
  – Piyush Divyanakar
  Jul 20 at 8:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @PiyushDivyanakar This is not a programming question. This is a numerical linear algebra question. Why is every time someone asks a numerical analysis question people attempt to close it?
  – RHowe
  Jul 20 at 15:02
  

  
  
  
  

1

1

I'm voting to close this question as off-topic because this is question about a design choice in programming and should be moved to stackoverflow.
– Piyush Divyanakar
Jul 20 at 8:20

I'm voting to close this question as off-topic because this is question about a design choice in programming and should be moved to stackoverflow.
– Piyush Divyanakar
Jul 20 at 8:20

@PiyushDivyanakar This is not a programming question. This is a numerical linear algebra question. Why is every time someone asks a numerical analysis question people attempt to close it?
– RHowe
Jul 20 at 15:02

@PiyushDivyanakar This is not a programming question. This is a numerical linear algebra question. Why is every time someone asks a numerical analysis question people attempt to close it?
– RHowe
Jul 20 at 15:02

add a comment | 

2 Answers
2

active

oldest

votes

up vote
0
down vote

If say $lambda$ is an eigen value of $A$. Then eigen vector is the solution to the equation $(A-lambda I)v=0$. This is basically null-space of $(A-lambda I)$. If $lambda$ is a repeated eigen-value you will get more than one eigen-vector iff, the null space of $A-lambda I$ has dimension greater than $1$. So it is possible that a root is repeated two times but has only one eigen-vector. This is the math part of the problem.

Note that eigen-values are unique but eigen-vectors aren't. So if $v_1$ is an eigen vector then so is $2v_1$. How exactly it is represented is design choice for programming. Looking at your results I would say they are chosen so that magnitude, i.e $|v_1|=1$.

share|cite|improve this answer

answered Jul 20 at 7:16

Piyush Divyanakar

3,258122

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, it is a well-known fact that the eigenvectors displayed by MATLAB/numpy are scaled to have magnitude 1. What I am asking is why the above two vectors are displayed instead of say, the vector [1, 0.7071, 0.7071] (then normalized to have magnitude 1), which is also an eigenvector of the matrix above.
  – Rakesh Sinha
  Jul 20 at 7:49
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I had to guess I would say they reduce the matrix to Row Reduced Echelon Form. Where all leading coefficients are $1$ and all entries above and below them are $0$. Now when you set free variables you are very likely to get lot of vectors containing most entries as $0$. However to really find out how it is done you must look at octave's internal code. Because the same isn't available for matlab(i think). Or you can mail octave developers and ask them.
  – Piyush Divyanakar
  Jul 20 at 8:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Which matrix are you guessing is reduced to row reduced echelon form? Reducing the eigvecs matrix above to row reduced echelon form results in the identity matrix; that's not an operation that preserves the eigenvectors.
  – Rakesh Sinha
  Jul 20 at 8:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The $A-lambda I$ matrix
  – Piyush Divyanakar
  Jul 20 at 8:43
  

  
  
  
  

add a comment | 

up vote
0
down vote

The algorithm for finding the eigenvalues and eigenvectors doesn't, in fact, use the determinant. In fact, it doesn't use Gaussian Elimination like the person above says either.

It uses the QR decomposition. There is a series of Matlab codes here showing some examples. One is eigvecs and geometric multiplicity.

 function [S, D] = eigvec(A)

 % eigvec Eigenvectors and their geometric multiplicity.
 %
 % S = eigvec(A) returns the largest possible set of linearly
 % independent eigenvectors of A. 
 %
 % [S, D] = eigvec(A) also returns the corresponding eigenvalues
 % in the diagonal matrix D.
 % Each eigenvalue in D is repeated according to the number of its
 % linearly independent eigenvectors. This is its geometric multiplicity.
 %
 % Always A*S = S*D. If S is square then A is diagonalizable and
 % inv(S)*A*S = D = LAMBDA.

 [m, n] = size(A);
 I = eye(n);
 [evalues, repeats] = eigval(A);
 S = ; d = ;
 for k = 1 : length(evalues);
 s = nulbasis(A - evalues(k)*I);
 [ms, ns] = size(s);
 S = [S s];
 temp = ones(ns, 1) * evalues(k);
 d = [d; temp];
 end
 D = diag(d);

end

function [evalues, repeats] = eigval(A)

% eigval Eigenvalues and their algebraic multiplicity.
%
% evalues = eigval(A) returns the distinct eigenvalues of A,
% with duplicates removed and sorted in decreasing order.
%
% [evalues, repeats] = eigval(A) also returns the row vector
% repeats that gives the multiplicity of each eigenvalue.
% The sum of the multiplicities is n.
%
% Examples: Let A = eye(n) and B = diag([3 4]).
% For A, evalues is 1 and repeats is n.
% For B, evalues is [4; 3] and repeats is [1 1].

tol = sqrt(eps);
lambda = sort(eig(A));
lambda = round(lambda/tol) * tol;
%
% lambda gives all n eigenvalues (repetitions included).
%
evalues = unique(lambda);
evalues = flipud(evalues);
n = length(lambda);
d = length(evalues);
A = ones(n, 1) * evalues';
B = lambda * ones(1, d);
MATCH = abs(A-B) <= tol;
%
% MATCH is an n by d zero matrix except
% MATCH(i,j) = 1 when lambda(i) = evalues(j).
% Summing the columns gives the row vector repeats.
%
repeats = sum(MATCH);

end


function N = nulbasis(A)

% nulbasis Basis for nullspace.
%
% N = nulbasis(A) returns a basis for the nullspace of A
% in the columns of N. The basis contains the n-r special 
% solutions to Ax=0. freecol is the list of free columns.
%
% Example:
%
% >> A = [1 2 0 3;
% [0 0 1 4];
%
% >> N = nulbasis(A)
%
% N = [-2 -3] 
% [ 1 0]
% [ 0 -4]
% [ 0 1]
%
% See also fourbase.

[R, pivcol] = rref(A, sqrt(eps));
[m, n] = size(A);
r = length(pivcol);
freecol = 1:n;
freecol(pivcol) = ;
N = zeros(n, n-r);
N(freecol, : ) = eye(n-r);
N(pivcol, : ) = -R(1:r, freecol);
end

testing...

A = [2,0,0;0,2,0;0,1,1];
[evalues, repeats] = eigval(A)
[S, D] = eigvec(A)


S =

 1 0 0
 0 1 0
 0 1 1


D =

 2 0 0
 0 2 0
 0 0 1

comparing to matlab

>> [V,D] = eigs(A)

V =

 0 1.0000 0
 0 0 0.7071
 1.0000 0 0.7071


D =

 1 0 0
 0 2 0
 0 0 2

If you're asking to which eigenvector does each eigen value belong. It goes by order I believe. However the specifics are in Netlib.

share|cite|improve this answer

answered Jul 20 at 15:22

RHowe

1,000815

add a comment | 

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote

If say $lambda$ is an eigen value of $A$. Then eigen vector is the solution to the equation $(A-lambda I)v=0$. This is basically null-space of $(A-lambda I)$. If $lambda$ is a repeated eigen-value you will get more than one eigen-vector iff, the null space of $A-lambda I$ has dimension greater than $1$. So it is possible that a root is repeated two times but has only one eigen-vector. This is the math part of the problem.

Note that eigen-values are unique but eigen-vectors aren't. So if $v_1$ is an eigen vector then so is $2v_1$. How exactly it is represented is design choice for programming. Looking at your results I would say they are chosen so that magnitude, i.e $|v_1|=1$.

share|cite|improve this answer

answered Jul 20 at 7:16

Piyush Divyanakar

3,258122

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, it is a well-known fact that the eigenvectors displayed by MATLAB/numpy are scaled to have magnitude 1. What I am asking is why the above two vectors are displayed instead of say, the vector [1, 0.7071, 0.7071] (then normalized to have magnitude 1), which is also an eigenvector of the matrix above.
  – Rakesh Sinha
  Jul 20 at 7:49
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I had to guess I would say they reduce the matrix to Row Reduced Echelon Form. Where all leading coefficients are $1$ and all entries above and below them are $0$. Now when you set free variables you are very likely to get lot of vectors containing most entries as $0$. However to really find out how it is done you must look at octave's internal code. Because the same isn't available for matlab(i think). Or you can mail octave developers and ask them.
  – Piyush Divyanakar
  Jul 20 at 8:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Which matrix are you guessing is reduced to row reduced echelon form? Reducing the eigvecs matrix above to row reduced echelon form results in the identity matrix; that's not an operation that preserves the eigenvectors.
  – Rakesh Sinha
  Jul 20 at 8:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The $A-lambda I$ matrix
  – Piyush Divyanakar
  Jul 20 at 8:43
  

  
  
  
  

add a comment | 

up vote
0
down vote

If say $lambda$ is an eigen value of $A$. Then eigen vector is the solution to the equation $(A-lambda I)v=0$. This is basically null-space of $(A-lambda I)$. If $lambda$ is a repeated eigen-value you will get more than one eigen-vector iff, the null space of $A-lambda I$ has dimension greater than $1$. So it is possible that a root is repeated two times but has only one eigen-vector. This is the math part of the problem.

Note that eigen-values are unique but eigen-vectors aren't. So if $v_1$ is an eigen vector then so is $2v_1$. How exactly it is represented is design choice for programming. Looking at your results I would say they are chosen so that magnitude, i.e $|v_1|=1$.

share|cite|improve this answer

answered Jul 20 at 7:16

Piyush Divyanakar

3,258122

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, it is a well-known fact that the eigenvectors displayed by MATLAB/numpy are scaled to have magnitude 1. What I am asking is why the above two vectors are displayed instead of say, the vector [1, 0.7071, 0.7071] (then normalized to have magnitude 1), which is also an eigenvector of the matrix above.
  – Rakesh Sinha
  Jul 20 at 7:49
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I had to guess I would say they reduce the matrix to Row Reduced Echelon Form. Where all leading coefficients are $1$ and all entries above and below them are $0$. Now when you set free variables you are very likely to get lot of vectors containing most entries as $0$. However to really find out how it is done you must look at octave's internal code. Because the same isn't available for matlab(i think). Or you can mail octave developers and ask them.
  – Piyush Divyanakar
  Jul 20 at 8:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Which matrix are you guessing is reduced to row reduced echelon form? Reducing the eigvecs matrix above to row reduced echelon form results in the identity matrix; that's not an operation that preserves the eigenvectors.
  – Rakesh Sinha
  Jul 20 at 8:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The $A-lambda I$ matrix
  – Piyush Divyanakar
  Jul 20 at 8:43
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

If say $lambda$ is an eigen value of $A$. Then eigen vector is the solution to the equation $(A-lambda I)v=0$. This is basically null-space of $(A-lambda I)$. If $lambda$ is a repeated eigen-value you will get more than one eigen-vector iff, the null space of $A-lambda I$ has dimension greater than $1$. So it is possible that a root is repeated two times but has only one eigen-vector. This is the math part of the problem.

Note that eigen-values are unique but eigen-vectors aren't. So if $v_1$ is an eigen vector then so is $2v_1$. How exactly it is represented is design choice for programming. Looking at your results I would say they are chosen so that magnitude, i.e $|v_1|=1$.

share|cite|improve this answer

answered Jul 20 at 7:16

Piyush Divyanakar

3,258122

If say $lambda$ is an eigen value of $A$. Then eigen vector is the solution to the equation $(A-lambda I)v=0$. This is basically null-space of $(A-lambda I)$. If $lambda$ is a repeated eigen-value you will get more than one eigen-vector iff, the null space of $A-lambda I$ has dimension greater than $1$. So it is possible that a root is repeated two times but has only one eigen-vector. This is the math part of the problem.

Note that eigen-values are unique but eigen-vectors aren't. So if $v_1$ is an eigen vector then so is $2v_1$. How exactly it is represented is design choice for programming. Looking at your results I would say they are chosen so that magnitude, i.e $|v_1|=1$.

share|cite|improve this answer

answered Jul 20 at 7:16

Piyush Divyanakar

3,258122

share|cite|improve this answer

share|cite|improve this answer

answered Jul 20 at 7:16

Piyush Divyanakar

3,258122

answered Jul 20 at 7:16

Piyush Divyanakar

3,258122

answered Jul 20 at 7:16

Piyush Divyanakar

3,258122

3,258122

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, it is a well-known fact that the eigenvectors displayed by MATLAB/numpy are scaled to have magnitude 1. What I am asking is why the above two vectors are displayed instead of say, the vector [1, 0.7071, 0.7071] (then normalized to have magnitude 1), which is also an eigenvector of the matrix above.
  – Rakesh Sinha
  Jul 20 at 7:49
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I had to guess I would say they reduce the matrix to Row Reduced Echelon Form. Where all leading coefficients are $1$ and all entries above and below them are $0$. Now when you set free variables you are very likely to get lot of vectors containing most entries as $0$. However to really find out how it is done you must look at octave's internal code. Because the same isn't available for matlab(i think). Or you can mail octave developers and ask them.
  – Piyush Divyanakar
  Jul 20 at 8:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Which matrix are you guessing is reduced to row reduced echelon form? Reducing the eigvecs matrix above to row reduced echelon form results in the identity matrix; that's not an operation that preserves the eigenvectors.
  – Rakesh Sinha
  Jul 20 at 8:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The $A-lambda I$ matrix
  – Piyush Divyanakar
  Jul 20 at 8:43
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, it is a well-known fact that the eigenvectors displayed by MATLAB/numpy are scaled to have magnitude 1. What I am asking is why the above two vectors are displayed instead of say, the vector [1, 0.7071, 0.7071] (then normalized to have magnitude 1), which is also an eigenvector of the matrix above.
  – Rakesh Sinha
  Jul 20 at 7:49
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I had to guess I would say they reduce the matrix to Row Reduced Echelon Form. Where all leading coefficients are $1$ and all entries above and below them are $0$. Now when you set free variables you are very likely to get lot of vectors containing most entries as $0$. However to really find out how it is done you must look at octave's internal code. Because the same isn't available for matlab(i think). Or you can mail octave developers and ask them.
  – Piyush Divyanakar
  Jul 20 at 8:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Which matrix are you guessing is reduced to row reduced echelon form? Reducing the eigvecs matrix above to row reduced echelon form results in the identity matrix; that's not an operation that preserves the eigenvectors.
  – Rakesh Sinha
  Jul 20 at 8:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The $A-lambda I$ matrix
  – Piyush Divyanakar
  Jul 20 at 8:43
  

  
  
  
  

Yes, it is a well-known fact that the eigenvectors displayed by MATLAB/numpy are scaled to have magnitude 1. What I am asking is why the above two vectors are displayed instead of say, the vector [1, 0.7071, 0.7071] (then normalized to have magnitude 1), which is also an eigenvector of the matrix above.
– Rakesh Sinha
Jul 20 at 7:49

Yes, it is a well-known fact that the eigenvectors displayed by MATLAB/numpy are scaled to have magnitude 1. What I am asking is why the above two vectors are displayed instead of say, the vector [1, 0.7071, 0.7071] (then normalized to have magnitude 1), which is also an eigenvector of the matrix above.
– Rakesh Sinha
Jul 20 at 7:49

If I had to guess I would say they reduce the matrix to Row Reduced Echelon Form. Where all leading coefficients are $1$ and all entries above and below them are $0$. Now when you set free variables you are very likely to get lot of vectors containing most entries as $0$. However to really find out how it is done you must look at octave's internal code. Because the same isn't available for matlab(i think). Or you can mail octave developers and ask them.
– Piyush Divyanakar
Jul 20 at 8:19

If I had to guess I would say they reduce the matrix to Row Reduced Echelon Form. Where all leading coefficients are $1$ and all entries above and below them are $0$. Now when you set free variables you are very likely to get lot of vectors containing most entries as $0$. However to really find out how it is done you must look at octave's internal code. Because the same isn't available for matlab(i think). Or you can mail octave developers and ask them.
– Piyush Divyanakar
Jul 20 at 8:19

Which matrix are you guessing is reduced to row reduced echelon form? Reducing the eigvecs matrix above to row reduced echelon form results in the identity matrix; that's not an operation that preserves the eigenvectors.
– Rakesh Sinha
Jul 20 at 8:42

Which matrix are you guessing is reduced to row reduced echelon form? Reducing the eigvecs matrix above to row reduced echelon form results in the identity matrix; that's not an operation that preserves the eigenvectors.
– Rakesh Sinha
Jul 20 at 8:42

The $A-lambda I$ matrix
– Piyush Divyanakar
Jul 20 at 8:43

The $A-lambda I$ matrix
– Piyush Divyanakar
Jul 20 at 8:43

add a comment | 

up vote
0
down vote

The algorithm for finding the eigenvalues and eigenvectors doesn't, in fact, use the determinant. In fact, it doesn't use Gaussian Elimination like the person above says either.

It uses the QR decomposition. There is a series of Matlab codes here showing some examples. One is eigvecs and geometric multiplicity.

 function [S, D] = eigvec(A)

 % eigvec Eigenvectors and their geometric multiplicity.
 %
 % S = eigvec(A) returns the largest possible set of linearly
 % independent eigenvectors of A. 
 %
 % [S, D] = eigvec(A) also returns the corresponding eigenvalues
 % in the diagonal matrix D.
 % Each eigenvalue in D is repeated according to the number of its
 % linearly independent eigenvectors. This is its geometric multiplicity.
 %
 % Always A*S = S*D. If S is square then A is diagonalizable and
 % inv(S)*A*S = D = LAMBDA.

 [m, n] = size(A);
 I = eye(n);
 [evalues, repeats] = eigval(A);
 S = ; d = ;
 for k = 1 : length(evalues);
 s = nulbasis(A - evalues(k)*I);
 [ms, ns] = size(s);
 S = [S s];
 temp = ones(ns, 1) * evalues(k);
 d = [d; temp];
 end
 D = diag(d);

end

function [evalues, repeats] = eigval(A)

% eigval Eigenvalues and their algebraic multiplicity.
%
% evalues = eigval(A) returns the distinct eigenvalues of A,
% with duplicates removed and sorted in decreasing order.
%
% [evalues, repeats] = eigval(A) also returns the row vector
% repeats that gives the multiplicity of each eigenvalue.
% The sum of the multiplicities is n.
%
% Examples: Let A = eye(n) and B = diag([3 4]).
% For A, evalues is 1 and repeats is n.
% For B, evalues is [4; 3] and repeats is [1 1].

tol = sqrt(eps);
lambda = sort(eig(A));
lambda = round(lambda/tol) * tol;
%
% lambda gives all n eigenvalues (repetitions included).
%
evalues = unique(lambda);
evalues = flipud(evalues);
n = length(lambda);
d = length(evalues);
A = ones(n, 1) * evalues';
B = lambda * ones(1, d);
MATCH = abs(A-B) <= tol;
%
% MATCH is an n by d zero matrix except
% MATCH(i,j) = 1 when lambda(i) = evalues(j).
% Summing the columns gives the row vector repeats.
%
repeats = sum(MATCH);

end


function N = nulbasis(A)

% nulbasis Basis for nullspace.
%
% N = nulbasis(A) returns a basis for the nullspace of A
% in the columns of N. The basis contains the n-r special 
% solutions to Ax=0. freecol is the list of free columns.
%
% Example:
%
% >> A = [1 2 0 3;
% [0 0 1 4];
%
% >> N = nulbasis(A)
%
% N = [-2 -3] 
% [ 1 0]
% [ 0 -4]
% [ 0 1]
%
% See also fourbase.

[R, pivcol] = rref(A, sqrt(eps));
[m, n] = size(A);
r = length(pivcol);
freecol = 1:n;
freecol(pivcol) = ;
N = zeros(n, n-r);
N(freecol, : ) = eye(n-r);
N(pivcol, : ) = -R(1:r, freecol);
end

testing...

A = [2,0,0;0,2,0;0,1,1];
[evalues, repeats] = eigval(A)
[S, D] = eigvec(A)


S =

 1 0 0
 0 1 0
 0 1 1


D =

 2 0 0
 0 2 0
 0 0 1

comparing to matlab

>> [V,D] = eigs(A)

V =

 0 1.0000 0
 0 0 0.7071
 1.0000 0 0.7071


D =

 1 0 0
 0 2 0
 0 0 2

If you're asking to which eigenvector does each eigen value belong. It goes by order I believe. However the specifics are in Netlib.

share|cite|improve this answer

answered Jul 20 at 15:22

RHowe

1,000815

add a comment | 

up vote
0
down vote

The algorithm for finding the eigenvalues and eigenvectors doesn't, in fact, use the determinant. In fact, it doesn't use Gaussian Elimination like the person above says either.

It uses the QR decomposition. There is a series of Matlab codes here showing some examples. One is eigvecs and geometric multiplicity.

 function [S, D] = eigvec(A)

 % eigvec Eigenvectors and their geometric multiplicity.
 %
 % S = eigvec(A) returns the largest possible set of linearly
 % independent eigenvectors of A. 
 %
 % [S, D] = eigvec(A) also returns the corresponding eigenvalues
 % in the diagonal matrix D.
 % Each eigenvalue in D is repeated according to the number of its
 % linearly independent eigenvectors. This is its geometric multiplicity.
 %
 % Always A*S = S*D. If S is square then A is diagonalizable and
 % inv(S)*A*S = D = LAMBDA.

 [m, n] = size(A);
 I = eye(n);
 [evalues, repeats] = eigval(A);
 S = ; d = ;
 for k = 1 : length(evalues);
 s = nulbasis(A - evalues(k)*I);
 [ms, ns] = size(s);
 S = [S s];
 temp = ones(ns, 1) * evalues(k);
 d = [d; temp];
 end
 D = diag(d);

end

function [evalues, repeats] = eigval(A)

% eigval Eigenvalues and their algebraic multiplicity.
%
% evalues = eigval(A) returns the distinct eigenvalues of A,
% with duplicates removed and sorted in decreasing order.
%
% [evalues, repeats] = eigval(A) also returns the row vector
% repeats that gives the multiplicity of each eigenvalue.
% The sum of the multiplicities is n.
%
% Examples: Let A = eye(n) and B = diag([3 4]).
% For A, evalues is 1 and repeats is n.
% For B, evalues is [4; 3] and repeats is [1 1].

tol = sqrt(eps);
lambda = sort(eig(A));
lambda = round(lambda/tol) * tol;
%
% lambda gives all n eigenvalues (repetitions included).
%
evalues = unique(lambda);
evalues = flipud(evalues);
n = length(lambda);
d = length(evalues);
A = ones(n, 1) * evalues';
B = lambda * ones(1, d);
MATCH = abs(A-B) <= tol;
%
% MATCH is an n by d zero matrix except
% MATCH(i,j) = 1 when lambda(i) = evalues(j).
% Summing the columns gives the row vector repeats.
%
repeats = sum(MATCH);

end


function N = nulbasis(A)

% nulbasis Basis for nullspace.
%
% N = nulbasis(A) returns a basis for the nullspace of A
% in the columns of N. The basis contains the n-r special 
% solutions to Ax=0. freecol is the list of free columns.
%
% Example:
%
% >> A = [1 2 0 3;
% [0 0 1 4];
%
% >> N = nulbasis(A)
%
% N = [-2 -3] 
% [ 1 0]
% [ 0 -4]
% [ 0 1]
%
% See also fourbase.

[R, pivcol] = rref(A, sqrt(eps));
[m, n] = size(A);
r = length(pivcol);
freecol = 1:n;
freecol(pivcol) = ;
N = zeros(n, n-r);
N(freecol, : ) = eye(n-r);
N(pivcol, : ) = -R(1:r, freecol);
end

testing...

A = [2,0,0;0,2,0;0,1,1];
[evalues, repeats] = eigval(A)
[S, D] = eigvec(A)


S =

 1 0 0
 0 1 0
 0 1 1


D =

 2 0 0
 0 2 0
 0 0 1

comparing to matlab

>> [V,D] = eigs(A)

V =

 0 1.0000 0
 0 0 0.7071
 1.0000 0 0.7071


D =

 1 0 0
 0 2 0
 0 0 2

If you're asking to which eigenvector does each eigen value belong. It goes by order I believe. However the specifics are in Netlib.

share|cite|improve this answer

answered Jul 20 at 15:22

RHowe

1,000815

add a comment | 

up vote
0
down vote

up vote
0
down vote

The algorithm for finding the eigenvalues and eigenvectors doesn't, in fact, use the determinant. In fact, it doesn't use Gaussian Elimination like the person above says either.

It uses the QR decomposition. There is a series of Matlab codes here showing some examples. One is eigvecs and geometric multiplicity.

 function [S, D] = eigvec(A)

 % eigvec Eigenvectors and their geometric multiplicity.
 %
 % S = eigvec(A) returns the largest possible set of linearly
 % independent eigenvectors of A. 
 %
 % [S, D] = eigvec(A) also returns the corresponding eigenvalues
 % in the diagonal matrix D.
 % Each eigenvalue in D is repeated according to the number of its
 % linearly independent eigenvectors. This is its geometric multiplicity.
 %
 % Always A*S = S*D. If S is square then A is diagonalizable and
 % inv(S)*A*S = D = LAMBDA.

 [m, n] = size(A);
 I = eye(n);
 [evalues, repeats] = eigval(A);
 S = ; d = ;
 for k = 1 : length(evalues);
 s = nulbasis(A - evalues(k)*I);
 [ms, ns] = size(s);
 S = [S s];
 temp = ones(ns, 1) * evalues(k);
 d = [d; temp];
 end
 D = diag(d);

end

function [evalues, repeats] = eigval(A)

% eigval Eigenvalues and their algebraic multiplicity.
%
% evalues = eigval(A) returns the distinct eigenvalues of A,
% with duplicates removed and sorted in decreasing order.
%
% [evalues, repeats] = eigval(A) also returns the row vector
% repeats that gives the multiplicity of each eigenvalue.
% The sum of the multiplicities is n.
%
% Examples: Let A = eye(n) and B = diag([3 4]).
% For A, evalues is 1 and repeats is n.
% For B, evalues is [4; 3] and repeats is [1 1].

tol = sqrt(eps);
lambda = sort(eig(A));
lambda = round(lambda/tol) * tol;
%
% lambda gives all n eigenvalues (repetitions included).
%
evalues = unique(lambda);
evalues = flipud(evalues);
n = length(lambda);
d = length(evalues);
A = ones(n, 1) * evalues';
B = lambda * ones(1, d);
MATCH = abs(A-B) <= tol;
%
% MATCH is an n by d zero matrix except
% MATCH(i,j) = 1 when lambda(i) = evalues(j).
% Summing the columns gives the row vector repeats.
%
repeats = sum(MATCH);

end


function N = nulbasis(A)

% nulbasis Basis for nullspace.
%
% N = nulbasis(A) returns a basis for the nullspace of A
% in the columns of N. The basis contains the n-r special 
% solutions to Ax=0. freecol is the list of free columns.
%
% Example:
%
% >> A = [1 2 0 3;
% [0 0 1 4];
%
% >> N = nulbasis(A)
%
% N = [-2 -3] 
% [ 1 0]
% [ 0 -4]
% [ 0 1]
%
% See also fourbase.

[R, pivcol] = rref(A, sqrt(eps));
[m, n] = size(A);
r = length(pivcol);
freecol = 1:n;
freecol(pivcol) = ;
N = zeros(n, n-r);
N(freecol, : ) = eye(n-r);
N(pivcol, : ) = -R(1:r, freecol);
end

testing...

A = [2,0,0;0,2,0;0,1,1];
[evalues, repeats] = eigval(A)
[S, D] = eigvec(A)


S =

 1 0 0
 0 1 0
 0 1 1


D =

 2 0 0
 0 2 0
 0 0 1

comparing to matlab

>> [V,D] = eigs(A)

V =

 0 1.0000 0
 0 0 0.7071
 1.0000 0 0.7071


D =

 1 0 0
 0 2 0
 0 0 2

If you're asking to which eigenvector does each eigen value belong. It goes by order I believe. However the specifics are in Netlib.

share|cite|improve this answer

answered Jul 20 at 15:22

RHowe

1,000815

The algorithm for finding the eigenvalues and eigenvectors doesn't, in fact, use the determinant. In fact, it doesn't use Gaussian Elimination like the person above says either.

It uses the QR decomposition. There is a series of Matlab codes here showing some examples. One is eigvecs and geometric multiplicity.

 function [S, D] = eigvec(A)

 % eigvec Eigenvectors and their geometric multiplicity.
 %
 % S = eigvec(A) returns the largest possible set of linearly
 % independent eigenvectors of A. 
 %
 % [S, D] = eigvec(A) also returns the corresponding eigenvalues
 % in the diagonal matrix D.
 % Each eigenvalue in D is repeated according to the number of its
 % linearly independent eigenvectors. This is its geometric multiplicity.
 %
 % Always A*S = S*D. If S is square then A is diagonalizable and
 % inv(S)*A*S = D = LAMBDA.

 [m, n] = size(A);
 I = eye(n);
 [evalues, repeats] = eigval(A);
 S = ; d = ;
 for k = 1 : length(evalues);
 s = nulbasis(A - evalues(k)*I);
 [ms, ns] = size(s);
 S = [S s];
 temp = ones(ns, 1) * evalues(k);
 d = [d; temp];
 end
 D = diag(d);

end

function [evalues, repeats] = eigval(A)

% eigval Eigenvalues and their algebraic multiplicity.
%
% evalues = eigval(A) returns the distinct eigenvalues of A,
% with duplicates removed and sorted in decreasing order.
%
% [evalues, repeats] = eigval(A) also returns the row vector
% repeats that gives the multiplicity of each eigenvalue.
% The sum of the multiplicities is n.
%
% Examples: Let A = eye(n) and B = diag([3 4]).
% For A, evalues is 1 and repeats is n.
% For B, evalues is [4; 3] and repeats is [1 1].

tol = sqrt(eps);
lambda = sort(eig(A));
lambda = round(lambda/tol) * tol;
%
% lambda gives all n eigenvalues (repetitions included).
%
evalues = unique(lambda);
evalues = flipud(evalues);
n = length(lambda);
d = length(evalues);
A = ones(n, 1) * evalues';
B = lambda * ones(1, d);
MATCH = abs(A-B) <= tol;
%
% MATCH is an n by d zero matrix except
% MATCH(i,j) = 1 when lambda(i) = evalues(j).
% Summing the columns gives the row vector repeats.
%
repeats = sum(MATCH);

end


function N = nulbasis(A)

% nulbasis Basis for nullspace.
%
% N = nulbasis(A) returns a basis for the nullspace of A
% in the columns of N. The basis contains the n-r special 
% solutions to Ax=0. freecol is the list of free columns.
%
% Example:
%
% >> A = [1 2 0 3;
% [0 0 1 4];
%
% >> N = nulbasis(A)
%
% N = [-2 -3] 
% [ 1 0]
% [ 0 -4]
% [ 0 1]
%
% See also fourbase.

[R, pivcol] = rref(A, sqrt(eps));
[m, n] = size(A);
r = length(pivcol);
freecol = 1:n;
freecol(pivcol) = ;
N = zeros(n, n-r);
N(freecol, : ) = eye(n-r);
N(pivcol, : ) = -R(1:r, freecol);
end

testing...

A = [2,0,0;0,2,0;0,1,1];
[evalues, repeats] = eigval(A)
[S, D] = eigvec(A)


S =

 1 0 0
 0 1 0
 0 1 1


D =

 2 0 0
 0 2 0
 0 0 1

comparing to matlab

>> [V,D] = eigs(A)

V =

 0 1.0000 0
 0 0 0.7071
 1.0000 0 0.7071


D =

 1 0 0
 0 2 0
 0 0 2

If you're asking to which eigenvector does each eigen value belong. It goes by order I believe. However the specifics are in Netlib.

share|cite|improve this answer

answered Jul 20 at 15:22

RHowe

1,000815

share|cite|improve this answer

share|cite|improve this answer

answered Jul 20 at 15:22

RHowe

1,000815

answered Jul 20 at 15:22

RHowe

1,000815

answered Jul 20 at 15:22

RHowe

1,000815

1,000815

add a comment | 

add a comment |