为什么用矩阵能计算游览路线的数目

小明将跟着爸爸从北京到南方旅行。他们打算游览南京、苏州、上海、杭州等四个城市。这四个城市之间，除了有铁路相通之外，苏州到杭州之间有内河轮船相通，杭州到南京则辟有航空线。

小明的爸爸选择了这样的旅行路线：先到上海办点事，然后坐火车到杭州，从杭州乘轮船到苏州，最后到南京。旅行社同志给他们送来一张联运票，这张票正是按上述路线预先印好了的。小明问爸爸，旅行社怎么预先就知道我们会走这样的路线。爸爸回答说，旅行社同志早就计算出各种游览路线的数目，每种游览路线预先都印好票子，需要时就能立即拿来出售。爸爸还说，各种各样的游览路线非常多，在数学上利用矩阵计算，就可以很快得出结果。

那么，旅行社的同志是怎样计算的呢？

先考虑最简单的情况我们把从一个城市到相邻的另一个城市（单程）称做一级路。例如从上海到苏州有一条一级路，但从上海到南京没有一级路（因为中间要经过苏州或杭州）。如果我们把各城市之间的一级路数目用表格形式列出来，就是表一。表中第一行有四个数0，1，0，1，分别表示南京到苏州、杭州有一条一级路，到上海没有一级路。

一级路比较单纯，一看就知道。把表一的各个数字排起来，成为四行四列的方阵T₁。这种排成方形（或矩形）的数字阵称为矩阵，横的叫行，竖的称为列。

现在考虑二级路。我们把连续走两段一级路的路称为二级路。例如从上海到南京有两条二级路：上海——苏州——南京，上海——杭州——南京。上海到苏州有一条二级路：上海-一杭州——苏州。特别是上海到上海也有两条二级路：上海——杭州——上海，上海一一苏州——上海。也就是说从一城市到相邻城市一来一回应算二级路。二级路总共有多少条？我们不妨再用观察法，把四城市之间的所有二级路都找出来，列成表二。

列表二就比列表一吃力了，弄不好还会漏算一条。如果城市数多，问题更复杂。假使我们要考虑三级路，四级路（即连续旅行三或四段一级路所成的路线），凭观察法会越来越困难。在数学上解决这个问题的办法，是引进矩阵的乘法。那时只要把一级路矩阵自乘，就得到T₂:T₁·T₁=T₁2=T₂。那么，究竟什么是矩阵相乘呢。为了简单起见，我们先讲两行两列的矩阵乘法。

设有两个矩阵A和B:

A=;B=

我们把A·B定义为：

C=A·B==。

具体作法是：把A的第一行（A=a₁₁，a₁₂)和B的第一列（b₁₁，b₂₁)中两个数先分别相乘再加起来，作为乘积矩阵C的C₁₁，把A的第一行和B的第二列中两个数分别相乘再加起来作为依次类推，得到C₂₁和C₂₂，它们分别处于矩阵的四个角。下面是一个具体数字的例子。

设A=，B=，则

C=。

现在再回到四行四列的矩阵上来。位于矩阵第i行第j列处的元素记为C_ij。我们有如下的乘法定义：

A·B==C，

和两行两列矩阵的乘法一样。其中，C₁₁=a₁₁b₁₁+a₁₂b₂₁+a₁₃b₃₁+a₁₄b₄₁，C₁₂=a₁₁b₁₂+a₁₂b₂₂+a₁₃b₃₂+a₁₄b₄₂，…依次类推，反正总是A的第i行和B的第j列各数字分别相乘然后相加构成C_ij。这样就把矩阵的乘法定义好了。现在我们把两个一级路矩阵相乘：

T₂=T₁·T₁=

这是因为的第一行和T₁的第一列相乘是0×0+1×1+0×0+1×1=2，第一行乘第二列得0×1+1×0+0×1+1×l=l，…，第二行乘第二列是1×l+0×0+l×l+l×l=3，依此类推，得到的T₁·T₁恰巧是我们计算过的表二和T₂。现在让我们来计算三级路矩阵

T₃=T₁·T₁·T₁=T₁·T₂=

它说明从南京到南京的三级路有两条：南京——杭州——苏州——南京，以及南京——苏州——杭州——南京。而上海到南京的三级路也有两条：（1）上海——杭州——苏州——南京，（2）上海——苏州——杭州——南京。从上海到杭州则有五条：（1）上海——苏州——南京——杭州，（2）上海——杭州——苏州——杭州，（3）上海——杭州——南京——杭州，（4）上海——苏州——上海——杭州，（5）上海——杭州——上海——杭州。三级路线数目又比二级路线多得多了，但用矩阵乘法很快可以算出。

矩阵是数学中十分有用的计算工具。计算游览路线的数目只是其中很小的应用。但仅从这个例子中可以看到，它能有效地帮助我们进行计算。如果有电子计算机帮助，当游览点多，路的级数高，靠观察简直无法算得清时，矩阵计算可以大大减轻人们的劳动。

细心的读者可能注意到，我们的路线矩阵从左上角到右下角的对角线都是对称的：即C_ij=C_ji。这是因为从上海到南京和从南京到上海的路线数目一样的缘故。可是，路线的情况可以各种各样，如何求前页下面两个交通图的路线矩阵？你不妨试试看。