The ordinary concept of a multiple-valued matrix is generalized by introducing non-deterministic matrices (Nmatrices), in which non-deterministic computations of truthvalues are allowed. The induced logics are investigated, and a generalized compactness theorem that applies to all finite Nmatrices is proved. Among the applications, it is shown that some important logics for reasoning under uncertainty can be characterized by finite Nmatrices but not by finite ordinary matrices.