ماتریس ها ساختار هایی انتزاعی مانند گراف ها هستند که در بسیاری از علوم کاربرد دارند. ماتریس ها پایه جبر خطی هستند که در الگوریتم های هوش مصنوعی و یادگیری ماشین بسیار به کار می روند. در المپیاد نیز ماتریس ها در الگوریتم های پیچیده مانند FFT به کار می روند و آشنایی با آن ها برای یک دانش آموز المپیادی مفید است.
در این فصل، با ماتریس ها آشنایی مختصری پیدا می کنیم و سپس به بررسی رابطه بین ماتریس ها و گراف ها می پردازیم تا به کمک آن ها بتوانیم الگوریتم های سریعی برای چند مساله ارائه کنیم.
هر آرایش مستطیل شکل از عدد های حقیقی، که شامل تعدادی سطر و ستون است یک ماتریس است. به هر عدد حقیقی واقع در هر ماتریس یک درایه آن ماتریس می گوییم.
\(\begin{equation*} A = \begin{bmatrix} 12 & 78 & -120 \\ 3.7 & -809 & 5 \end{bmatrix} \end{equation*}\) \(\begin{equation*} B = \begin{bmatrix} 1 & 3 \\ 4 & 2 \end{bmatrix} \end{equation*}\) \(\begin{equation*} C = \begin{bmatrix} -0.5 & -90 \\ 0 & 4.09 \\ 5 & 6 \\ 92 & 37 \end{bmatrix} \end{equation*}\)
ماتریسی که m ستون و n سطر دارد را از مرتبه n × m می خوانیم.
برای جمع دو ماتریس در گام اول باید توجه کنیم که تعداد سطر های دو ماتریس و تعداد ستون های دو ماتریس با هم برابر باشند(لزومی ندارد که تعداد سطر ها با تعداد ستون ها برابر باشد). در قدم بعدی هر درایه ماتریس A با درایه متانظر در ماتریس B جمع می شود و درایه متانظر در C را می سازد. عملیات تفریق نیز به همین روش انجام می شود.
\(\begin{equation*} \begin{bmatrix} 2 & 4 \\ 1 & 3 \end{bmatrix} + \begin{bmatrix} 3 & 2 \\ 4 & 1 \end{bmatrix} = \begin{bmatrix} 5 & 6 \\ 5 & 4 \end{bmatrix} \end{equation*}\)
\(\begin{equation*} \begin{bmatrix} 37 & 7 \\ 0 & 3 \end{bmatrix} - \begin{bmatrix} 6 & 13 \\ 2 & -5 \end{bmatrix} = \begin{bmatrix} 31 & -6 \\ -2 & 8 \end{bmatrix} \end{equation*}\)
برای ضرب ماتریس ها در ابتدا باید توجه داشت که اگر ماتریس A، n سطر و m ستون داشته باشد ماتریس B باید m سطر و z ستون داشته باشد. در این صورت ماتریس C که حاصل ضرب این دو ماتریس است n سطر و z ستون دارد. درایه \(c_{ij}\) برابر است با جمع \(a_{ik} × b_{kj}\) که در آن k یک عدد طبیعی است که حداکثر مقدار آن m است.
\(\begin{equation*} \begin{bmatrix} 4 & 2 & 3 \\ 0 & 3 & -1 \end{bmatrix} \begin{bmatrix} 7 \\ -5 \\ 10 \end{bmatrix} = \begin{bmatrix} 48 \\ -25 \end{bmatrix} \end{equation*}\)
هنگامی که یک عدد حقیقی k در یک ماتریس ضرب می شود تمامی درایه آن ماتریس در k ضرب می شود.
\(\begin{equation*} 5 \begin{bmatrix} 0 & 1 \\ 2 & 3 \end{bmatrix} = \begin{bmatrix} 0 & 5 \\ 10 & 15 \end{bmatrix} \end{equation*}\)