How do you notate a sum of only some of the elements of an array?

Question

So, for one of my university courses, I have to analyse an algorithm on one of my assignments and identify a loop invariant that would allow for a formal proof of algorithmic correctness.

I believe that I identified it in the form of a sum of all of the elements of an array A that have positive values, ranging from 0 to i (where i is the number of time the algorithm has iterated).

I know how to annotate most of that - you write a capital sigma with “k=0” as a subscript and i as a superscript, followed by A[k] but I’m not sure how to specify that I’m only summing the positive elements, so the kth element of A is only added to the sun if it has a positive value.

The lecturer has assured me that that’s not a problem since I can just explain my answer in words, but I still sort of want to know how to do it properly.

Answer 1

Mathematically an array is typically treated as a vector, and is indexed to indicate where in the array/vector you are. You've written $A[k]$ in your question, but I would suggest that, at least for this part of your analysis, you use a subscript instead and let your vector be $A = (A_1, A_2 \ldots ,A_n)$. Each iteration of the vector can then be written as $A^{(k)}$ and any individual element of the $k^{th}$ iterate can be written as $A^{(k)}_j$.

So, with this notation set up, the positive elements of the array are those where $A_j > 0$.

EDIT: from the comments, it's now clear that you want to add the $k^{th}$ element of the array to the overall sum only after $k$ iterations, and if it's positive.

$$\sum_{j=0}^i \max \{0,A^{(j)}_j\}$$ or, if you want to avoid using additional functions (such as $\max$):

$$\sum_{\stackrel{j=0}{A^{(j)}_j >0}} A^{(j)}_j$$

i.e. the sum of those elements of the array $A$ summed if the $k^{th}$ element is positive after $k$ iterations. (If I might offer some additional advice use $T$ for final time rather than $i$).

Answer 2

For your next question, please consider using LaTeX notation for the Math part. Just write stuff between two dollar signs! Weird symbols are written with "\". Quick cheat-sheet here: http://web.ift.uib.no/Teori/KURS/WRK/TeX/symALL.html

If I got you correctly, you want to sum all elements on a vector $(x_0, ...x_n)$ removing the negative ones. Well, let $f:\mathbb{R} \rightarrow \mathbb{R}$ where $f(x)=x$ if $x>0$ and $f(x)=0$ otherwise. Now you can write your sum as:

$\sum_{k=0}^{n} x_{k}f(x_k)$

Answer 3

I can't think of an elegant way to do this. You could define a set $S$ by the following:

$$S = \{ \text{all} \; k \; \text{such that} \; A[k] > 0 \}$$

Then your desired sum would have the form

$$\sum_{k \in S} A[i]$$

though this isn't much more elegant than really just explaining it in words.

---

Another way that comes to mind is sort of inspired by the Kronecker delta (in a very tangential way, it was merely what made me think of this approach, even if the two are fairly different in a literal sense).

Let's say your array has $n$ elements, $A[1],A[2],...,A[n]$. Define a sequence of corresponding values $a_1,...,a_n$ by the following:

$$a_k = \left\{\begin{matrix} A[k] & A[k]>0\\ 0 & A[k] \le 0 \end{matrix}\right.$$

where $k=1,2,...,n.$ Then your sum is simply

$$\sum_{k=0}^n a_k$$

in that case.

---

Personally I'm with your lecturer in the sense that, unless you're doing some sort of further manipulation with these sums, it's better to just say it words. Seems like defining it symbolically, while possible, doesn't really achieve anything meaningfully different, in the sense that the information communicated is the same.

Matter of opinion though, I suppose.

Answer 4

There are many, many different ways of notating such an expression, none of them particularly "standard". Mathematical notation is not as agreed-upon as it seems from most undergrad and earlier experience. More algorithmic things are even less agreed-upon. There is no "proper" way short of defining your notation.

At any rate, probably the most "usual" approach would be to define a separate function by cases using a notation like $f(x)=\begin{cases}x,& x>0\\ 0,& x\leq 0\end{cases}$. Then your expression would be $\sum_{k=0}^i f(A[k])$. (Actually, Eevee Trainer's suggestion of defining the sequence $a_k$ is even more likely.) This is not particularly pleasant as we need to define a separate function, and it doesn't really "filter out" from the sum, it just makes the undesired entries $0$. There are some notations to do something like this inline, but they aren't particularly widespread and wouldn't be understood without explanation. One example is $\sum_{k=0}^i (A[k]>0\to A[k];0)$.

A more direct rendition would be to use a notation like $\sum_{k=0,A[k]>0}^i A[k]$ or many variations on this. I'd be more inclined to write this more like $\sum_{k\in[i], A[k]>0}A[k]$ or $\sum\{A[k]\mid k\in [i] \land A[k]>0\}$. Variations on notation like this are reasonably widespread, but there isn't a "standard" way. Most mathematicians would be able to figure out what was intended.

For your particular problem, we can do something a bit hacky to get what you want with notation that is covered in high school. Namely, $\sum_{k=0}^i (|A[k]|+A[k])/2$. Closely related would be $\sum_{k=0}^i \max(0,A[k])$. These are not general solutions for filtering by arbitrary predicates, of course. That said, it can often be valuable to be able to express functions this way, but in most cases it would just be obfuscatory.

In a more computer science context, there is also tons of notation inspired by various programming languages.