  In this paper we compute the minimum degree of a faithful representation by
partial transformations of a finite semigroup admitting a faithful completely
reducible matrix representation over the field of complex numbers. This
includes all inverse semigroups, and hence our results generalize earlier
results of Easdown and Schein on the minimal faithful degree of an inverse
semigroup. It also includes well-studied monoids like full matrix monoids over
finite fields and the monoid of binary relations (i.e., matrices over the
Boolean semiring). Our answer reduces the computation to considerations of
permutation representations of maximal subgroups that are faithful when
restricted to distinguished normal subgroups. This is analogous to (and
inspired by) recent results of the second author on the minimal number of
irreducible constituents in a faithful completely reducible complex matrix
representation of a finite semigroup that admits one. To illustrate what
happens when a finite semigroup does not admit a faithful completely reducible
representation, we compute the minimum faithful degree of the opposite monoid
of the full transformation monoid.
