In the present communication, we introduce Pythagorean fuzzy soft matrix and its various possible types. Some binary operations and various properties over the matrices are also being defined with their proof of validity. Further, the Pythagorean fuzzy soft matrices have been taken into account for proposing a new algorithm for decision making by using choice matrix and weighted choice matrix. In addition to this, an algorithm for medical diagnosis problem by making use of score matrix and utility matrix has also been proposed. Numerical examples for each of the applications have been successfully illustrated. A comparative analysis with other existing methods has also been carried out.