If you have enough time then go ahead with the documentation of test sscenarios that you plan to execute.Or else directly start with test cases if you are confident of your test team . Traceability Matrix can be done in parallel so as to make sure that you not miss out any requirement.
If there is any QA standard in your company then you should follow the process and should start with the step defined in process.
If there is not any standard process then you should start with writing test cases becoz by doing this you can get a better understanding of the application. And you can take a idea that in which part you can findout more bugs or where is the possibility to find more Bugs. And you should make RTM after write complete test cases bbecoz the main motive of the RTM is to verify that have you cover all the requirements of the application to test through test cases.