# Finding null vectors of a parameter-dependent matrix

I have dense complex matrices $M(z)$ in which each element $M_{ij} = M_{ij}(z)$ depends on a complex parameter $z$. I need to find $z$ such that the matrix $M$ gets singular, i.e. I am looking for null vectors $\vec v$ which satisfy $M(z) \vec k = \vec 0$.

So far, I use a Newton method. As the wanted $M(z)$ is singular, I need $M$'s determinant to vanish. Starting with an initial guess $z_0$, I iterate $$z_{i+1} = z_i - \frac{g(z_i)}{g'(z_i)}$$ with $g(z) := \det M(z)$. To avoid computing the determinant from definition, I use LU factorization. The iteration is stopped when $|z_{i+1} - z_{i}|$ is sufficiently small.

Using the matrix identity $\frac{\mathrm{d}}{\mathrm{d}z}\ln \det M(z) = \mathrm{trace}\,(M^{-1}(z) M'(z))$, the reciprocal logarithmic derivative in the iteration formula can replaced to yield $$z_{i+1} = z_i - \frac{1}{\mathrm{trace}\,(M^{-1}(z) M'(z))}\,,$$ which is what I use in the end.

A few details on steps involved: so far, I compute all derivatives $g'(z)$ from a forward finite difference scheme $g'(z) = \frac{g(z + h) - g(z)}{h} - \mathrm{i}\frac{g(z + \mathrm{i}h) - g(z)}{h}$, ($h$ real), likewise for derivatives of $M$. Also note I'm assuming that singular vectors have multiplicity $m = 1$ (although adaptation of the formulas above is possible using $g=(\det M(z))^m$.

The matrix $M$ has no special structure in global (i.e. not Hermitian). Depending on the problem, it may be rectangular or square. In any case, it is dense and well-conditioned. Typical sizes range from ~ $100\times100$ to $10k \times 10k$. $M$'s origin is in the boundary element method. For open systems (that may have resonances), the null vectors I am looking are the resonance wavefunctions on the boundaries of the domains under consideration.

I'd like to learn about alternative methods of adjusting the parameter $z$ such that $M$ gets singular. Do you have any other ideas? Or any comments on the method I described? Although the results are fine, I don't like the approach too much as both iterations described here involve a step that is essentially $O(N^3)$ (LU or the inverse). Furthermore, for the second scheme, I need to compute the inverse of near singular matrices.

• Is M Hermitian? Could you something about where $M$ arises from? What are the typical dimensions of $M$? Further, do you run into problems as the iterations progress and the matrix becomes singular? May 5, 2014 at 14:16
• @user2457602, I have added more information to the question as you requested. I typically do not run into problems in the iteration. May 5, 2014 at 15:03

Edit: Note that your formula for the finite difference approximation of $g'$ does not need the imaginary correction (just the first term is enough) if your function is analytic. If you can compute the derivatives analytically or automatically (with automatic differentiation), then that would be much better. However, I would guess this is not possible if your matrix comes from a BEM discretization.