  We propose a graph theoretic approach to determine trace of product of two
permutation matrices through a weighted digraph representation of the
permutation matrices. Consequently, we derive trace-zero doubly stochastic (DS)
matrices of order $5$ whose $k$-th power is also a trace-zero DS matrix for
$k\in\{2,3,4,5\}$. Then, we determine necessary conditions for the coefficients
of a generic polynomial of degree $5$ to be realizable as the characteristic
polynomial of a trace-zero DS matrix of order $5$. Finally, we approximate the
eigenvalue region of trace-zero DS matrices of order $5.$
