# IsTotallyNonsingular

 Other toolboxes required IsTotallyNonsingular Determines whether or not a matrix is totally nonsingular none IsTotallyPositive 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:

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