J'ai l'impression que le MAX7219 ne s'alimente pas en dessous de 4V.
Donc ce ne sera pas possible d'alimenter en 3.3V.
Partant sur du 5V, on peut envisager plusieurs 18650 en parallèle avec un régulateur élévateur (step-up) ou une batterie plomb avec un abaisseur (step-down).
Ne te fie pas aux vendeurs du type AliExpress qui t'anoncent des batteries 18650 à 9000mAH. C'est du flan.
Une 18650 fait au maxi 3000mAH pour les meilleures. Il faut de la marque connue dont tu peux obtenir la datasheet.
Une batterie plomb sera de préférence choisie parmi les modèles dits cycliques, plus chers.
Comme c'est vraiment cher, partons sur de la 18650.
Un chargeur solaire pour batterie 18650, cela se trouve facilement.
Disons que pour 1.3A sous 5V, en misant sur 90% de rendement au niveau régulateur, il te faudra au minimum un panneau de 7W pour alimenter de jour.
Si tu veux recharger une batterie en même temps, il faudra plus d'énergie.
Pour fonctionner pendant deux heures de nuit, tu vas avoir besoin de 2x1.3A = 2.6AH, donc en gros une ou deux 18650 de bonne qualité.
Si tu répartis le courant de charge sur minimum 4H, le besoin est de 0.65A.
Il faudrait en gros 3W pour charger la batterie, car il faut charger vite, il ne fait pas toujours beau ...
Le panneau ferait donc au moins 10W, donc pas du tout 30x30cm, beaucoup plus.
De plus, sous un arbre, il ne faut pas y compter. Impossible.
Enfin, si tu alimentes le tout sur batterie pendant la nuit, il faudra que l'ARDUINO mesure la tension batterie, afin de couper les LEDs en dessous d'une certaine tension, 2.5V pour une 18650, et que l'ARDUINO se mette en veille pour na plus consommer.
Une UNO ne fera pas l'affaire, je te conseille un ARDUINO MINI. Consommation en veille qq µA.
Comme tu le vois, cela n'a l'air de rien, mais ce n'est pas si simple.
J'espère ne pas t'avoir découragé. 
@+