Hola:
La idea es que identifiques las clases que formarán parte de tu modelo y les asignes responsabilidades acordemente. Una vez identificadas las posibles clases necesitarás implementar sus métodos y escribir las pruebas unitarias que muestren su comportamiento. En tu análisis veo que hablás mucho de una "matriz", por lo que asumo que estás considerando crear una clase que se llame Matriz, aunque habría que ver si es necesario que se llame así y qué cosas hará.
Por otro lado, en cuanto a los diagramas, la pregunta de si deben ser "en lapiz y papel o usando UML" no tiene mucho sentido. UML es el lenguaje que provee un estándar para varios tipos de diagramas en la ingeniería de software. Existen herramientas de software que te permiten crear esos diagramas (como por ejemplo Astah, ArgoUML o simplemente draw.io) pero para este tipo de ejercicios alcanza con que los hagan en papel a mano alzada.
Saludos,
Tomás