Maji\cite{maj-13}, firstly proposed neutrosophic soft sets can handle the indeterminate information and inconsistent information which exists commonly in belief systems. In this paper, we have firstly redefined complement, union and compared our definitions of neutrosophic soft with the definitions given by Maji. Then, we have introduced the concept of neutrosophic soft matrix and their operators which are more functional to make theoretical studies in the neutrosophic soft set theory. The matrix is useful for storing an neutrosophic soft set in computer memory which are very useful and applicable. Finally, based on some of these matrix operations a efficient methodology named as NSM-decision making has been developed to solve neutrosophic soft set based group decision making problems.