ماتریس و عملیات های روی آن

ماتریس ها ساختار هایی انتزاعی مانند گراف ها هستند که در بسیاری از علوم کاربرد دارند. ماتریس ها پایه جبر خطی هستند که در الگوریتم های هوش مصنوعی و یادگیری ماشین بسیار به کار می روند. در المپیاد نیز ماتریس ها در الگوریتم های پیچیده مانند 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*}\)