5
$\begingroup$

my question is between mathematics, physics and informatics. Suppose i have an Hamiltonian (hermitian matrix) that i can diagonalize. The matrix that allows this transformation is a unitary matrix build with the eigenvectors of my Hamiltonian.

Now suppose I select only the $n$ first eigenvectors of length $m$. The matrix $A$ can be build with those eigenvectors, it's size is $m\times n$ with $m>n$. The eigenvectors are the column of the $A$ matrix. The $n$ eigenvectors are of course linearly independent.

Then, I select $n$ rows of my $A$ matrix and build $B$, a new $n\times n$ matrix. It is logic that $B$ can be such that $\det(B)=0$.

Here is my question : Is there a way (using Lapack if possible) to select randomly the rows in order to be sure that $\det(B)\neq0$ ?

|cite|improve this question
$\endgroup$
5
$\begingroup$

Yes. Simply run $n$ steps of column-pivoted QR on the adjoint of your matrix. You may want to look into zgeqp3.

If you express the result of the pivoted $QR$ decomposition as: $$ A^H \Omega = Q R, $$ your $B$ matrix will be the adjoint of the left-most $n$ columns of $A^H \Omega$, as $\Omega$ is a permutation matrix.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ thx for your answer but I'll need a bit more help ! what will I get after the n steps ? are you sure that this answer is the one I need ? I mean, I need to build the $B$ matrix by selecting (randomly) $n$ rows in such a way that $B$ is invertible... $\endgroup$ – PinkFloyd Jun 24 '13 at 21:21
  • $\begingroup$ Pivoted QR decompositions are precisely what you need, as each iteration finds the remaining column which is maximally-independent from the previous ones in the two-norm. The result of $n$ steps of column-pivoted QR on your $n \times m$ matrix $A^H$ is $A^H \Omega \approx Q R$, where $\Omega$ is $m \times m$ (with its bottom-right $m-n$ submatrix equal to the identity), $Q$ is $n \times n$, and $R$ is $n \times m$, with its left-most $n \times n$ submatrix upper-triangular (and invertible). You should be able to figure things out from here. $\endgroup$ – Jack Poulson Jun 24 '13 at 21:56
  • $\begingroup$ okay thanks. I'm sorry but i'm not sure that i understood everything... dealing with matrices is not what i do in my everyday life... where is the random part of this algorithm. if i run twice the same algorithm, it seems to me that i will get twice the same answer... because of what you said in the comment @Wolfgang. Moreover, what is my $B$ matrix? is it $Q$ ? or should i build it using $\Omega$ and $A^H$ ? $\endgroup$ – PinkFloyd Jun 25 '13 at 12:13
  • $\begingroup$ There is no randomness here (and I'm not sure why you feel that you need it). Your $B$ matrix is the adjoint of the leftmost $n$ columns of $A^H \Omega$, as $\Omega$ is a permutation matrix. $\endgroup$ – Jack Poulson Jun 25 '13 at 15:27
  • $\begingroup$ because i know that i can build a lot of different $B$ matrices using $n$ rows of $A$, and i just need to find one of those $B$. this $B$ matrix will be the starting point of a Markov chain (but that's another story) and i need a random starting point. Maybe it was confusing, but $B$ is not the matrix that contains the maximum number of rows of $A$, thus it is not unique. $\endgroup$ – PinkFloyd Jun 25 '13 at 21:47
2
$\begingroup$

I think if I understand your (long) question correctly, then here is a summary of it: You have a matrix $A\in {\mathbb R}^{n\times m}, n>m$ with full column rank. Can I find a subset ${\cal I}\subset [1,n], |{\cal I}|=m$ of rows of $A$ that are linearly independent?

If so, then here's an algorithm: Start with ${\cal I}=\{\}$ and repeat:

  • add a new row if it is linearly independent of the previous rows;
  • if $|{\cal I}|=m$ then you're done
  • otherwise, if no new vector could be found that is linearly independent of the previous ones, drop the element last added to the index set and add a different vector

This is essentially a depth first search through a tree whose terminal nodes represent all $m$-tuples of rows and tries to find the first one that contains $m$ linearly independent trees, pruning those sub-trees where less than $m$ vectors are already linearly dependent.

This may not be an efficient algorithm, but it should work just fine for small $m$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is roughly what a pivoted QR decomposition does, but each iteration selects the remaining column whose projection onto the orthogonal complement of the space spanned by the previous columns is maximal (in the two-norm). $\endgroup$ – Jack Poulson Jun 24 '13 at 23:13
  • $\begingroup$ this is indeed what i want to do ! but will this alogorithm work ? i mean, at the third step, if i can't find a vector that is linearly independent from all the others, is it enough to remove only the previous one, or should i remove all of them. $\endgroup$ – PinkFloyd Jun 25 '13 at 11:56
  • $\begingroup$ @JackPoulson: Yes, that's a better strategy. It doesn't guarantee that it will be faster, but it's more likely because you prioritize vectors that are maximally linearly independent. $\endgroup$ – Wolfgang Bangerth Jun 25 '13 at 13:45
  • $\begingroup$ @user2110463: It's a backtracking search through the tree of possibilities. You need to remove only the last and if you can't find any alternative vector, then you would also remove the second to last, etc. $\endgroup$ – Wolfgang Bangerth Jun 25 '13 at 13:46
  • $\begingroup$ okay that's what i thought... the good point of your method is that it looks to be random, a requirement that, as far as i understand, Jack's method lacks... $\endgroup$ – PinkFloyd Jun 25 '13 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.