Q: Check if a matrix is Positive Semidefinite I have a question concerning the check whether a given matrix is positive semidefinite or not. In mathematica the function PositiveDefiniteMatrixQ[m] tells me whether the matrix m is positive, but not semidefinite. I wanted to ask whether there exists an implementation for that purpose, and if not, how to implement a code that is as fast as possible.

A: One can add a small addition:
semiPositiveDefiniteMatrixQ[m_, tol_: 10.^-10] := 
   PositiveDefiniteMatrixQ[m + tol IdentityMatrix@Dimensions[m]]

PositiveDefiniteMatrixQ@{{1, 0}, {0, 0}}
semiPositiveDefiniteMatrixQ@{{1, 0}, {0, 0}}


False
True

Explanation:
Let the matrix $M$ has $\lambda_1, \lambda_2, \dots \lambda_n$ eigenvalues. Then the matrix $M+tI$ ($I$ is the identity matrix) has $\lambda_1+t, \lambda_2+t, \dots \lambda_n+t$ eigenvalues. If $M+tI$ is positive definite and $t>0$ is small enough (depends on the working precision) then $M$ is positive semidefinite.

A: There is now a function PositiveSemidefiniteMatrixQ that does this.

A: Here is a method that computes only the smallest eigenvalue and checks that it's greater or equal to zero. This can be done by using a shift as in this answer, or for large matrices by using the option Method -> {"Arnoldi", "Criteria" -> "RealPart"} for Eigenvalues:
Clear@positiveSemiDefiniteQ
positiveSemiDefiniteQ[mat_?MatrixQ] := (
       First@Eigenvalues[N[mat] + # IdentityMatrix[Dimensions[mat]], 
        1] - #) >= 0. &@Norm[Flatten[mat]]

positiveSemiDefiniteQ[{{1, 0}, {1, 1}}]

(* ==> True *)

The Arnoldi method isn't usable for the small matrix in this example, so I decided to post this more general approach. The difference to the other Eigenvalues based solution is that I only need one eigenvalue, after I make the shift that guarantees that all eigenvalues are sorted properly.

A: Computing the eigenvalues is actually overkill. It could be done by row reduction. For convenience, I set empty list to be positive semidefinite.
psdcheck[m_]:=(
  If[Length@m== 0,Return@True];
  If[Length@m== 1,Return@If[Negative@m[[1,1]],False,True]];
  If[Or@@(Negative@Diagonal@m),Return@False];

  Module[{mtemp,ind1},
    mtemp=If[SymmetricMatrixQ@m,m,(#+Transpose@#)&@m];
    ind1=Flatten@Position[Diagonal@mtemp,diag_/;diag== 0.];

    If[Length@ind1!=0,
      If[(#!=ConstantArray[0.,Dimensions@#])&@(mtemp[[ind1]]),Return@False,
        mtemp=mtemp[[#,#]]&@Complement[Range@Length@mtemp,ind1];
        If[Length@mtemp<= 1,Return@psdcheck@mtemp]];];

  psdcheck[mtemp[[2;;,2;;]]-
    (Outer[Times,#,#/mtemp[[1,1]]])&@mtemp[[1,2;;]]]
])


A: If your matrix is numeric, the following should be a reasonably fast way to determine positive semi-definiteness:
Clear@positiveSemiDefiniteQ
positiveSemiDefiniteQ[mat_?MatrixQ] := 
    With[{eigs = Chop@Eigenvalues@N@mat},
        Quiet[
            Check[
                And @@ Thread[eigs >= 0],
                False,
                GreaterEqual::nord
            ],
            GreaterEqual::nord
        ]
    ]


A: Here's a function that checks to see if the roots of the characteristic polynomial are all non-negative (as suggested by Daniel Lichtblau:
semiDefQ[m_] := Module[{p, roots},
   p[x_] := CharacteristicPolynomial[m, x];
   roots = Chop[Roots[p[z] == 0, z] // N];
   Length[Select[Apply[List, roots[[All, 2]]], # ∈ Reals && # >= 0 &]] == n]

To use, just input your favorite matrix
n = 3;
m = RandomInteger[{0, 10}, {n, n}];
semiDefQ[m]

