IsTotallyNonsingular

From QETLAB
Jump to: navigation, search
IsTotallyNonsingular
Determines whether or not a matrix is totally nonsingular

Other toolboxes required none
Related functions IsTotallyPositive
Function category Miscellaneous

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.

Syntax

  • ITN = IsTotallyNonsingular(X)
  • ITN = IsTotallyNonsingular(X,SUB_SIZES)
  • ITN = IsTotallyNonsingular(X,SUB_SIZES,TOL)
  • [ITN,WIT] = IsTotallyNonsingular(X,SUB_SIZES,TOL)

Argument descriptions

Input arguments

  • 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.

Output arguments

  • 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.

Examples

The Fourier matrix

A well-known result of Cebotarev says that the quantum Fourier matrix is totally nonsingular in prime dimensions[1], which we can verify in the 5-by-5 case as follows:

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:

>> F = FourierMatrix(6);
>> [itn,wit] = IsTotallyNonsingular(F)
 
itn =
 
     0
 
 
wit =
 
     1     3
     1     4
 
>> F([1,3],[1,4])
 
ans =
 
   0.4082             0.4082          
   0.4082             0.4082

Almost all matrices are totally nonsingular

A randomly-chosen matrix will, with probability 1, be totally nonsingular:

>> IsTotallyNonsingular(randn(10))
 
ans =
 
     1

Notes

In practice, this function is practical for matrices of size up to about 15-by-15.

Source code

Click on "expand" to the right to view the MATLAB source code for this function.

  1. %%  ISTOTALLYNONSINGULAR    Determines whether or not a matrix is totally nonsingular
  2. %   This function has one required argument:
  3. %     X: a matrix
  4. %
  5. %   ITN = IsTotallyNonsingular(X) is either 1 or 0, indicating that X is or
  6. %   is not totally nonsingular (i.e., all of its square submatrices are
  7. %   nonsingular, within reasonable numerical error).
  8. %
  9. %   This function has two optional input arguments:
  10. %     SUB_SIZES (default 1:min(size(X)))
  11. %     TOL (default max(size(X))*eps(norm(X,'fro')))
  12. %
  13. %   [ITN,WIT] = IsTotallyNonsingular(X,SUB_SIZES,TOL) determines whether or
  14. %   not every r-by-r submatrix of X is nonsingular, where r ranges over all
  15. %   values in the vector SUB_SIZES, and nonsingularity is determined within
  16. %   a tolerance of TOL. If ITN = 0 then WIT is a matrix with two rows and r
  17. %   columns that specifies an r-by-r submatrix of X that is singular.
  18. %
  19. %   URL: http://www.qetlab.com/IsTotallyNonsingular
  20.  
  21. %   requires: opt_args.m, sporth.m
  22. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  23. %   package: QETLAB
  24. %   last updated: December 13, 2012
  25.  
  26. function [itn,wit] = IsTotallyNonsingular(X,varargin)
  27.  
  28. sX = size(X);
  29. wit = 0;
  30.  
  31. % set optional argument defaults: sub_sizes=1:min(size(X)), tol=max(size(X))*eps(norm(X,'fro'))
  32. [sub_sizes,tol] = opt_args({ 1:min(sX), max(sX)*eps(norm(X,'fro')) },varargin{:});
  33.  
  34. for j = 1:length(sub_sizes)
  35.     % 1x1 rank can be computed quickly, so do it separately
  36.     if(sub_sizes(j) == 1)
  37.         [r,c] = find(abs(X) < tol,1);
  38.         if(min(size(r)) > 0)
  39.             itn = 0;
  40.             wit = [r;c];
  41.             return;
  42.         end
  43.  
  44.     % larger ranks are slower; just loop on through!
  45.     else
  46.         sub_ind_r = nchoosek(1:sX(1),sub_sizes(j));
  47.         if(sX(1) == sX(2)) % nchoosek is slightly slow, so only call it once if we can get away with it
  48.             sub_ind_c = sub_ind_r;
  49.         else
  50.             sub_ind_c = nchoosek(1:sX(2),sub_sizes(j));
  51.         end
  52.         sub_ind_len_r = size(sub_ind_r,1);
  53.         sub_ind_len_c = size(sub_ind_c,1);
  54.         for kr = 1:sub_ind_len_r
  55.             for kc = 1:sub_ind_len_c
  56.                 % Using det to test for singularity of a matrix is much
  57.                 % faster, but much more error-prone than other functions
  58.                 % like rank or cond. Thus we use det in general for speed
  59.                 % reasons, and then double-check any results we are unsure
  60.                 % of via rank (this gets us the best of both worlds).
  61.                 if(abs(det(X(sub_ind_r(kr,:),sub_ind_c(kc,:)))) < tol)
  62.                     [~,rnk] = sporth(X(sub_ind_r(kr,:),sub_ind_c(kc,:)),tol);
  63.                     if(rnk < sub_sizes(j))
  64.                         itn = 0;
  65.                         wit = [sub_ind_r(kr,:);sub_ind_c(kc,:)];
  66.                         return;
  67.                     end
  68.                 end
  69.             end
  70.         end
  71.     end
  72. end
  73.  
  74. itn = 1;

References

  1. M. Newman. On a theorem of Cebotarev. Linear Multilinear Algebra, 3:259–262, 1976.