We study Nijenhuis operators, that is, (1,1)-tensors with vanishing Nijenhuis
torsion under the additional assumption that they are gl-regular, i.e., every
eigenvalue has geometric multiplicity one. We prove the existence of a
coordinate system in which the operator takes first or second companion form,
and give a local describtion of such operators. We apply this local description
to study singular points. In particular, we obtain their normal forms in
dimension two and discover topological restrictions for the existence of
gl-regular Nijenhuis operators on closed surfaces. This paper is an important
step in the research programme suggested in arXiv:1903.04603 and
arXiv:1903.06411.