Row/Column Transformations II
It seems relevant to repeatedly pick
a row or a column whose sum is negative, and apply the operator on that row/
column. Will a series of such operator
applications always yield the desired goal?
To answer the latter question, we may try
using some means for following algorithmic progress. We may use a metric, which
involves some selected value that will
“progress” upon the algorithmic execution,
towards the final goal.
What should a suitable metric be here?
Our problem involves sums of rows and
columns. Will it be helpful to focus on the
sums of specific rows and columns? Not
quite. But, keeping as metric the sum of
all the rows may be very helpful. This sum
is the total sum of the matrix integers. A
single operator application, on a row/column whose sum is negative, increases the
metric value (the total matrix sum), since
the sum of the corresponding row/column
increases, and no matrix cells are changed
other than those in that row/column.
A series of repeated operator applications on negative-sum rows and columns
repeatedly increases the value of our
selected metric. This sum may not grow
indefinitely, as it is bounded by the sum of
the absolute values of the matrix integers!
Thus, this process of “incrementations,” of
the matrix sum, is finite, and will eventually
terminate. And when it terminates, there
will be no rows or columns whose sums
are negative. Notice that we do not really
care for the final value of the metric (the
total matrix sum) upon termination, as it is
sufficient for us only to see that the “
incre-mentation” process eventually ends.
Any algorithm that yields termination
involves “incrementations” of the total
matrix sum. What is a lower bound on the
number of necessary operator applications? There may be matrices for which,
no matter what algorithm is applied, at
least N operator applications are required.
Such matrices are, for example, the matrices in which all the integer values are
negative (and a single operator application
“touches” only N matrix cells at a time).
Thus, N is surely a lower bound for the
number of operator applications. Is this
lower bound tight? Can we develop an
algorithm that will not require more than
N operator applications for every initial
matrix? (Since we focus on the number of
operator applications, we “do not count”
extra computations. So, maybe it will be
beneficial to always select the row or
column with the most negative sum? Will
such an algorithm never require more than
N operator applications?) Perhaps there
are initial cases for which any algorithm
will require more than N operator applica-
tions? We leave these questions open for
the interested reader.
All in all, we provided an analysis that
focused on the characteristic of a given
operator. The examination of the operator’s utilization was tied to the notion of a
metric. The notion of a metric is employed
in various ways by computer scientists,
and one way of using it is in the examination of algorithmic progress, such as
the one displayed here. The selection of
a suitable metric here yielded an elegant
termination argumentation, of an offered
algorithmic process. The argumentation
involved a “don’t care” notion in the sense
of not seeking a concrete, actual value for
the metric upon termination. We noticed
that at least N operator applications may
be necessary in some cases, and left open
the question whether this value is a tight
lower bound for obtaining the desired goal
for all cases.
DOI: 10.1145/3106013 Copyright held by author.