0
$\begingroup$

I would like to know the complexity of multiplying a matrix of $n\times m$ size by a scalar $\alpha$?

In fact, I have a directed graph $G=(V,E)$ represented by an incidence matrix $M$. I would like to calculate the transpose of this graph, i.e., inverse the directions of the edges. I think that if I multiply $M$ by $-1$ I will get the transposed graph. Am I right?

  • If I am right, what is the complexity of multiplying a matrix by a scalar?
  • If I am not, where is my mistake and what is the complexity of multiplying a matrix by a scalar anyway?

I think the complexity is $\Theta(n\cdot m)$.

Thanks.

$\endgroup$
  • 3
    $\begingroup$ Multiplying by $-1$ is not the same of transposing. Transposing is an operation in its own right and can not be achieved using operations like matrix addition and (scalar) multiplication. The exact complexity of these operations depends on the computational model you use, and if you don't specify there's no way to answer this question definitively. But $O(nm)$ is a very reasonable time complexity for transposing. $\endgroup$ – Tom van der Zanden Apr 5 '15 at 18:31
  • $\begingroup$ @TomvanderZanden I am not sure what you mean by "he exact complexity of these operations depends on the computational model you use," See the note at the end of my answer. $\endgroup$ – babou Apr 6 '15 at 22:17
  • 1
    $\begingroup$ @babou. Perhaps Tom was noting the difference between the model where one counts multiplication as one step as opposed to the log-cost model where multiplication of two $b$-bit numbers counts $O(b^2)$ or $O(b\log b)$ steps, depending on how one implements multiplication. $\endgroup$ – Rick Decker Apr 6 '15 at 23:55
2
$\begingroup$

In general, if you have an $n\times m$ matrix $A=(a_{i,j})$ with $1\le i\le n$ and $1\le j\le m$ then there will be $nm$ entries in the array. To multiply $A$ by a scalar $c$ you multiply each element by c, which (assuming multiplication can be done in constant time) will take $nm$ multiplications. That's not the way to go, though, if $A$ is the adjacency matrix of a directed graph.

For your peoblem, if $A$ is the adjacency matrix of a digraph $G$ on $n$ vertices, then $A$ will be an $n\times n$ matrix $(a_{i, j})$ with $a_{i,j}=1$ when there is a directed edge $e=(i, j)$ from vertex $i$ to vertex $j$ and $a_{i,j}=0$ otherwise. You correctly note that the reversed graph $G'$ will have an adjacency matrix $B=(b_{i,j})$ which is the transpose of $A$, so we'll have $b_{i, j} = a_{j, i}$, since $G'$ will have an edge from vertex $v_i$ to vertex $v_j$ if and only if $G$ has an edge from $v_j$ to $v_i$. To get the transpose of $A$, then, we'll swap $a_{i, j}\leftrightarrow a_{j, i}$ entries of $A$. There will be $n(n-1)/2$ swaps needed, since we swap every element above the main diagonal with its corresponding entry below the main diagonal.

Note that multiplying $A$ by $-1$ won't work, since the entries of an adjacency matrix must be only $1$ or $0$.

$\endgroup$
1
$\begingroup$

Of course, as previously noted by other users, you cannot transpose a matrix by a simple multiplication by a scalar. Transposition is an operation of its own.

The complesity of matrix operations depends on the way the matrices are represented.

The cost of matrix operations is very dependent on the way matrices are actually represented in your algorithm. While the most obvious representations can have a cost $O(nm)$ (or $O(n^2)$ for a square matrix) for scalar multiplication or for transposition, other representations can be chosen, depending on the algorithm it is used for, with a lower cost.

The complexity of multiplying a matrix by a scalar $\alpha$ in the usual way does imply multiplying each of its $n\times m$ elements by $\alpha$, and hence has a cost $O(nm)$. However, in general, the cost depends on the way you actually represent matrices, and it is conceivable to use representations where the cost might be constant, if the matrix is represented up to scalar multiplication together with a scalar factor. The computational cost can also be lower in the case of a sparse matrix representation that allows iterating only on the useful (or non-zero) elements.

Without going into details, matrix transposition can also be done in constant time, i.e., complexity $O(1)$, if you choose to represent a matrix as a pair composed of an appropriate memory structure of elements, and an indexation function for accessing them, given the row and column number. Then transposition can be achieved in constant time simply by changing the indexation function.

Note: this is a matter of representation, not of model of computation (the expression computational model being ambiguous). But I am not sure what is intended by Tom van der Zanden'comment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.