IsTotallyNonsingular

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, which we can verify in the 5-by-5 case as follows:

>> IsTotallyNonsingular(FourierMatrix(5))

ans =

     1

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 here to view this function's source code on github.