Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Randomized methods for rank-deficient linear systems

Published

Author(s)

Josef Sifuentes, Zydrunas Gimbutas, Leslie Greengard

Abstract

We present a simple, accurate method for solving consistent, rank-deficient linear systems, with or without additional rank-completing constraints. Such problems arise in a variety of applications, such as the computation of the eigenvectors of a matrix corresponding to a known eigenvalue. The method is based on elementary linear algebra combined with the observation that if the matrix is rank-k deficient, then a random rank k perturbation yields a nonsingular matrix with probability 1.
Citation
Electronic Transactions on Numerical Analysis
Volume
44

Keywords

eigenvectors, integral equations, nullspace, null vectors, randomized algorithms, rank-deficient systems.

Citation

Sifuentes, J. , Gimbutas, Z. and Greengard, L. (2015), Randomized methods for rank-deficient linear systems, Electronic Transactions on Numerical Analysis, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=915064 (Accessed December 7, 2021)
Created February 12, 2015, Updated October 12, 2021