Considering the case that we have a fixed set of training examples and a fixed ANN (i.e same number of input,output and intermediate layers). Is it possible that there exists more than one set of weights that all produce same desired results when applied to test examples. Basically can different weight matrix lead to same result behaviorally?
I am not an expert on this field, but I believe the answer is yes.
If you think of a Neural Net as drawing a plane between multiple datasets in a multidimensional space, you can visualize a way in which separable data can be divided by multiple planes.
If you take the degenerate example in which there are only two points plotted on a simple 2-dimensional graph, you could certainly have a wide range of NNs that would correctly separate these two points. As you increase the number of neurons in your network, you increase the number of dimensions across which you can separate data, but even fairly densely clustered data still has effectively infinite space between it at a given level of magnification, leaving space for all kinds of networks that correctly separate test data.
Looking at it another way, you can apply the pigeon-hole principle here. If there are only n permutations of classification and >n permutations of weights, then by definition at least 1 permutation will have multiple permutations of weights that select that classification. This is the case in most ANNs, in which you are classifying a comparatively finite set of inputs using a set of multiple neurons using floating point values.
As for the problem you're trying to actually solve, I am not sure that speed of your weights is a rational way to evaluate this problem. Different NN implementations may use different algorithms, but typically calculating an output using weights, even on a very complex NN is still quite fast. Once the weights have been calculated, it's just some simple multiplication to classify an entry.
The TRAINING process can be very time-intensive, however. The only way I can think of in which the weights affect your training process is with respects to which starting weights you choose. In this case, you could very well have "better" starting weights that result in a faster training process. The way to think of starting weights is like determining your location on a graph. Neural Network training algorithms try to work themselves into a minimum error state, and some weights are "closer" to a minimum than others. Also, some weights might put the training process into a situation where it is more likely to fall into local minima, which could make some starting weights more accurate than others.
That said, it's very difficult (not realistic?) to know for any given set of training data what your starting weights should be. You could randomly assign starting weights and train with each set to try and pinpoint the ideal training starting weight, but that weight would only be valid for that one set of training data on that specific neural network (and once you have trained the network, essentially your optimal starting weight IS a finished network).
So, ultimately, I'm not sure how useful this information will be for what you're trying to accomplish, but I'm interested in knowing more about what it is you think you might do!
Yes, it is absolutely possible. The best way to see why this is the case is to consider trivial cases. As always, remember the heuristic from mathematics: if you want to see whether a theorem is true, look first at some small examples. If you can find a small counterexample, then you know the theorem is false and you don't have to think about more complicated cases.
So, here is a very simple counterexample. Consider the trivial case where our training set has exactly one point in it (there's only one example in the training set). Then there certainly can be multiple weight settings that all reproduce that one example correctly.
For instance, suppose we have a neural network with one input, one output, and multiple layers. Suppose the neural network has dozens of intermediate nodes and connections. Then there are dozens of weights that can be chosen to try to fit the training set. We have dozens of degree of freedom.
Now suppose our training set has only a single point: the input $5$ should map to the output $7$. Well, it is immediately clear there there will be multiple settings of the weights, where each setting correctly causes the model to output $7$ when you give it the input $5$.
This is analogous to having a system of linear equations where you have more unknowns than equations: it's like you have a system of linear equations with dozens of unknowns and only one equation (one constraint). Such a system of linear equations has multiple valid solutions. Intuitively, when you have more degrees of freedom than constraints, typically you should expect there to be multiple solutions.