Constructive matrix theory for higher order interaction