|Determines whether or not a matrix is totally nonsingular|
|Other toolboxes required||none|
IsTotallyNonsingular is a function that determines whether or not a given matrix is totally nonsingular (i.e., all of its square submatrices are nonsingular). The input matrix can be either full or sparse.
- ITN = IsTotallyNonsingular(X)
- ITN = IsTotallyNonsingular(X,SUB_SIZES)
- ITN = IsTotallyNonsingular(X,SUB_SIZES,TOL)
- [ITN,WIT] = IsTotallyNonsingular(X,SUB_SIZES,TOL)
- X: A matrix.
- SUB_SIZES (optional, default 1:min(size(X))): A vector specifying the sizes of submatrices to be checked for nonsingularity.
- TOL (optional, default length(X)*eps(norm(X,'fro'))): The numerical tolerance used when determining nonsingularity.
- ITN: A flag (either 1 or 0) indicating that X is or is not totally nonsingular.
- WIT (optional): If ITN = 0 then WIT specifies a submatrix of X that is singular. More specifically, WIT is a matrix with 2 rows such that X(WIT(1,:),WIT(2,:)) is singular.
The Fourier matrix
When the dimension is composite, the Fourier matrix is not totally nonsingular. For example, the following code shows in the 6-dimensional case a 2-by-2 submatrix of the Fourier matrix that is singular:
Almost all matrices are totally nonsingular
A randomly-chosen matrix will, with probability 1, be totally nonsingular:
In practice, this function is practical for matrices of size up to about 15-by-15.
Click on "expand" to the right to view the MATLAB source code for this function.
%% ISTOTALLYNONSINGULAR Determines whether or not a matrix is totally nonsingular
% This function has one required argument:
% X: a matrix
% ITN = IsTotallyNonsingular(X) is either 1 or 0, indicating that X is or
% is not totally nonsingular (i.e., all of its square submatrices are
% nonsingular, within reasonable numerical error).
% This function has two optional input arguments:
% SUB_SIZES (default 1:min(size(X)))
% TOL (default max(size(X))*eps(norm(X,'fro')))
% [ITN,WIT] = IsTotallyNonsingular(X,SUB_SIZES,TOL) determines whether or
% not every r-by-r submatrix of X is nonsingular, where r ranges over all
% values in the vector SUB_SIZES, and nonsingularity is determined within
% a tolerance of TOL. If ITN = 0 then WIT is a matrix with two rows and r
% columns that specifies an r-by-r submatrix of X that is singular.
% URL: http://www.qetlab.com/IsTotallyNonsingular
% requires: opt_args.m, sporth.m
% author: Nathaniel Johnston (email@example.com)
% package: QETLAB
% last updated: December 13, 2012
function [itn,wit] = IsTotallyNonsingular(X,varargin)
sX = size(X);
wit = 0;
% set optional argument defaults: sub_sizes=1:min(size(X)), tol=max(size(X))*eps(norm(X,'fro'))
for j = 1:length(sub_sizes)
% 1x1 rank can be computed quickly, so do it separately
if(sub_sizes(j) == 1)
itn = 0;
wit = [r;c];
% larger ranks are slower; just loop on through!
sub_ind_r = nchoosek(1:sX(1),sub_sizes(j));
if(sX(1) == sX(2)) % nchoosek is slightly slow, so only call it once if we can get away with it
sub_ind_c = sub_ind_r;
sub_ind_c = nchoosek(1:sX(2),sub_sizes(j));
sub_ind_len_r = size(sub_ind_r,1);
sub_ind_len_c = size(sub_ind_c,1);
for kr = 1:sub_ind_len_r
for kc = 1:sub_ind_len_c
% Using det to test for singularity of a matrix is much
% faster, but much more error-prone than other functions
% like rank or cond. Thus we use det in general for speed
% reasons, and then double-check any results we are unsure
% of via rank (this gets us the best of both worlds).
[~,rnk] = sporth(X(sub_ind_r(kr,:),sub_ind_c(kc,:)),tol);
if(rnk < sub_sizes(j))
itn = 0;
wit = [sub_ind_r(kr,:);sub_ind_c(kc,:)];
itn = 1;
- M. Newman. On a theorem of Cebotarev. Linear Multilinear Algebra, 3:259–262, 1976.